Disk Intersection Graphs: Models, Data Structures, and Algorithms
Let P be a set of n point sites in the plane. The unit disk graph UD(P) on P has vertex set P and an edge between two sites p,q of P if and only if p and q have Euclidean distance |pq| <= 1. If we interpret P as centers of disks with diameter 1, then UD(P) is the intersection graph of these disks, i.e., two sites p and q form an edge if and only if their corresponding unit disks intersect. Two natural generalizations of unit disk graphs appear when we assign to each point p of P an associated radius r_p > 0. The
first one is the disk graph D(P), where we put an edge between p and q if and only if |pq| <= r_p + r_q, meaning that the disks with centers p and q and radii r_p and r_q intersect. The second one yields a directed graph on P, called the transmission graph of P. We obtain it by putting a directed edge from p to q if and only if |pq| <= r_p, meaning that q lies in the disk with center p and radius r_p. For disk and transmission graphs we define the radius ratio Psi to be the ratio of the largest and the smallest radius that is assigned to a site in P. It turns out that the radius ratio is an important measure of the complexity of the graphs and some of our results will depend on it.
For these three classes of disk intersection graphs we present data structures and algorithms that solve four types of graph theoretic problems: dynamic connectivity, routing, spanner construction, and reachability oracles; see below for details. For disk and unit disk graphs, we improve upon the currently best known results, while the problems we consider for transmission graphs abstain non-trivial solutions so far.
First, we present a data structure that maintains the connected components of a unit disk graph UD(P) when P changes dynamically. It takes O(log^2 n) amortized time to insert or delete a site in P and O(log(n)/loglog(n)) worst-case time to
determine if two sites are in the same connected component. Here, n is the maximum size of P at any time. A simple variant improves the amortized update time to O(log(n)loglog(n)) at the cost of a slightly increased worst-case query time of O(log(n)).
Using more advanced data structures, we can extend our approach to disk graphs. While the worst-case query time remains
O(log(n)/loglog(n)), an update now requires O(Psi^2 2^(alpha(n))log^(10)(n)) amortized expected time, where Psi is the radius ratio of the disk graph and alpha(n) is the inverse Ackermann function.
As the second problem, we consider routing in unit disk graphs. A routing scheme R for UD(P) assigns to each site s of P a
label l(s) and a routing table rho(s). For any two sites s and t of P, the scheme R must be able to route a packet from s to t in the following way: given a current site r (initially, r = s), a header h (initially empty), and the target label l(t), the scheme R may consult the current routing table rho(r) to compute a new site r' and a new header h', where r' is a neighbor of r in UD(P). The packet is then routed to r', and the process is repeated until the packet reaches t. The resulting sequence of sites is called the routing path. The stretch of R is the maximum ratio of the (Euclidean) length of the routing path produced by R and the shortest path in UD(P), over all pairs of distinct sites in P.
For any given eps > 0, we show how to construct a routing scheme for UD(P) with stretch 1+eps using labels of O(log(n)) bits and routing tables of O(eps^(-5)log^2(n)log^2(D)) bits, where D is the (Euclidean) diameter of UD(P). The header size is O(log(n)log(D)) bits.
Next, we construct sparse approximations of transmission and disk graphs. Let G be a transmission graph. A t-spanner for G is
a subgraph H of G with vertex set P so that for any two sites p and q of P, we have d_H(p, q) <= td_G(p, q), where d_H and
d_G denote the shortest path distance in H and G (with Euclidean edge lengths). We show how to compute a t-spanner for G with O(n) edges in O(n(log(n) + log(Psi))) time, where Psi is the radius ratio of P. Utilizing advanced data structures, we obtain a
construction that runs in O(n log^5(n)) time, independent of Psi. This construction can be adapted to disk graphs and gives a t-spanner for D(P) in expected time O(n2^(alpha(n))log^(10)(n)), where alpha(n) is the inverse Ackermann function.
As an application we show that our t-spanner can be used to find a BFS tree in a transmission or disk graph for any given start vertex in O(n log(n)) additional time.
Finally, we compute reachability oracles for transmission graphs. These are data structures that answer reachability queries: given two sites p and q, is there a directed path between them? The quality of an oracle is measured by the space S(n), the query time Q(n), and the preproccesing time. We present three reachability oracles whose quality depends on the radius ratio
Psi: the first one works only for Psi < sqrt(3) and achieves Q(n) = O(1) with S(n) = O(n) and preprocessing time O(n log(n));
the second data structure gives Q(n) = O(Psi^3 sqrt(n)) and S(n) = O(Psi^3 n^(3/2)); the third data structure is randomized with
Q(n) = O(n^(2/3)(log(n) + log(Psi))) and S(n) = O(n^(5/3)(log(n) + log(Psi))) and answers queries correctly with high probability.
As a second application for our spanners, we employ them to achieve a fast preprocessing time for our reachability oracles.