Anmerkungen:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Beschreibung:
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. Dynamic Connectivity: 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 ...