In the same way as the spread of computer networks has motivated the study of distributed algorithms, the increase in size of these networks and appearance of wireless networks has caused significant research interest in local algorithms, in which the decision at each node is computed based only on the information contained in the node's local neighbourhood (i.e. up to k hops away, for some constant k). Local algorithms are of particular interest in wireless ad-hoc networks (e.g. sensor networks), where the dynamic and transient nature of the network requires fast adaptability and severely limits applicability of centralized and global approaches.

However, there are strong limitations on what can be computed locally, typically caused by the underlying global nature of the problem (e.g. constructing a spanning tree) or by the possibility of local symmetry. One way to deal with the problem is a relaxation of the requirements on the solution (e.g. instead of finding a spanning tree, find a sufficiently sparse subgraph), another is to consider additional structural information available in the network to break the symmetry.

In this talk, we examine how geographic information (i.e. the nodes know their GPS coordinates - are location-aware) can be exploited in ad-hoc networks modeled by unit-disc graphs. We consider the problems of locally constructing suitable (planar, connected, with good spanner properties, of low cost) subgraphs of the underlying unit-disc graph, as well as various graph covering and colouring problems.