A spanner of a geometric graph G is a spanning subgraph S, such that the length of the shortest path between any two vertices in G is well approximated by the distance provided by a path in S. In particular, the distance in S must be stretched by no more than some constant factor beyond the distance in G. One of the main applications of spanners is to find a sparse communication graph for wireless networks. Often, the communication range of a broadcasting node is modeled by a disk centered on the node of radius 1, resulting in the unit disk graph G. It is known that this graph has a spanner of stretch factor (1 + &egr;) for any &egr; > 0, which can be constructed in O(n &egr;2) time.
The communication links in the unit disk graph are symmetric, so the graph G is undirected. This paper studies the case where the ranges are arbitrary, resulting in an undirected disk graph G. Spanning such a graph is more challenging. The authors establish that the disk graph has a spanner, again with stretch (1 + &egr;). It can be constructed within the same time bound, but now inflated by a factor of log R, where R is the largest disk radius, potentially the diameter of G. The algorithm partitions the edges by lengths into a logarithmic hierarchy, making decisions on which edges to include in the spanner based on nearest neighbors within one slice of the hierarchy.
In a subsequent preprint [1], the same authors show that their result cannot be improved for arbitrary metrics, but, for the Euclidean metric, the log R factor can be removed.
