Spanners for Geometric Intersection Graphs with Applications†

A disk graph is an intersection graph of a set of disks with arbitrary radii in the plane. Given a real number t> 1, we say that a subgraph G ′ of a graph G is a t-spanner for G, if for every pair of vertices u, v in G, there exists a path in G ′ of length at most t times the distance between u and v in G. In this paper, we consider the problem of efficient construction of sparse spanners of disk (ball) graphs with support for fast distance queries. These problems are motivated by issues arising from topology control and routing in wireless networks. We present the first algorithm for constructing spanners of ball graphs. For a ball graph in Rk, we construct a (1 + ǫ)-spanner for any ǫ> 0 with O(nǫ−k+1) edges in O(n2ℓ+δǫ−k logℓ S) expected time, using an efficient partitioning of space into hypercubes and solving intersection problems. Here ℓ = 1 − 1/(⌊k/2 ⌋ + 2), δ is any positive constant, and S is the ratio between the largest and smallest radius. For the special case where all the balls have the same radius, we show that the spanner construction has complexity almost equivalent to the construction of a Euclidean minimum spanning tree. The algorithm uses an efficient subdivision of space to construct a sparse graph having man