Unit disk graph
From Wikipedia, the free encyclopedia
In geometric graph theory, a unit disk graph is the intersection graph of a family of unit circles in the Euclidean plane. That is, we form a vertex for each circle, and connect two vertices by an edge whenever the corresponding circles cross each other.
There are several other possible definitions of a unit disk graph, equivalent to each other up to a choice of scale factor:
- An intersection graph of equal-radius circles, or of equal-radius disks
- A graph formed from a collection of equal-radius circles, in which two circles are connected by an edge if one circle contains the center of the other circle
- A graph formed from a collection of points in the Euclidean plane, in which two points are connected if their distance is below a fixed threshhold
Every induced subgraph of a unit disk graph is also a unit disk graph. An example of a graph that is not a unit disk graph is the star K1,7: if each of seven unit disks touches a common unit disk, some two of the seven disks must touch each other. Every unit distance graph, in which we connect two points in a planar point set if their distance is exactly one, is a unit disk graph, but the converse is not true; for instance, K4 is a unit disk graph but not a unit distance graph.
Beginning with the work of Huson and Sen (1995), unit disk graphs have been used in computer science to model the topology of ad-hoc wireless communication networks. In this application, nodes are connected through a direct wireless connection without a base station. It is assumed that all nodes are homogeneous and equipped with omnidirectional antennas. Node locations are modeled as Euclidean points, and the area within which a signal from one node can be received by another node is modeled as a circle. If all nodes have transmitters of equal power, these circles are all equal. Random geometric graphs, formed as unit disk graphs with randomly generated disk centers, have also been used as a model of percolation and various other phenomena (see, e.g., Dall and Christensen 2002).
It is NP-hard to determine whether a graph, given without geometry, can be represented as a unit disk graph (Breu and Kirkpatrick, 1998). However, many important and difficult graph optimization problems such as maximum independent set, graph coloring, and minimum dominating set can be approximated efficiently by using the geometric structure of these graphs (Marathe et al. 1994, Matsui 2000), and the maximum clique problem can be solved exactly for these graphs in polynomial time, given a disk representation (Clark, Colbourn, and Johnson 1990).
When a given vertex set forms a triangular lattice, a necessary and sufficient condition for the perfectness of a unit graph is known (Miyamoto and Matsui 2005). For the perfect case, the multicoloring problem is polynomially solvable.
[edit] References
- Breu, Heinz; Kirkpatrick, David G. (1998). "Unit disk graph recognition is NP-hard". Computational Geometry Theory and Applications 9 (1–2): 3–24.
- Clark, Brent N.; Colbourn, Charles J.; Johnson, David S. (1990). "Unit disk graphs". Discrete Mathematics 86 (1–3): 165–177. DOI:10.1016/0012-365X(90)90358-O.
- Dall, Jesper; Christensen, Michael (2002). "Random geometric graphs". Phys. Rev. E 66: 016121. arXiv:cond-mat/0203026.
- Huson, Mark L.; Sen, Arunabha (1995). "Broadcast scheduling algorithms for radio networks". Military Communications Conference, IEEE MILCOM '95, 647–651, vol. 2. DOI:10.1109/MILCOM.1995.483546.
- Marathe, Madhav V.; Breu, Heinz; Hunt, Harry B. III; Ravi, S. S.; Rosenkrantz, Daniel J. (1994). "Geometry based heuristics for unit disk graphs". arXiv:math.CO/9409226.
- Matsui, Tomomi (2000). "Approximation Algorithms for Maximum Independent Set Problems and Fractional Coloring Problems on Unit Disk Graphs". Lecture Notes in Computer Science 1763: 194-200.
- Miyamoto, Yuichiro; Matsui, Tomomi (2005). "Perfectness and Imperfectness of the kth Power of Lattice Graphs". Lecture Notes in Computer Science 3521: 233-242.
