Unit disk graph

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.

1 Characterizations
2 Properties
3 Applications
4 Computational complexity
5 See also
6 Notes
7 References

Characterizations

There are several possible definitions of the 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 threshold

Properties

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 K_1,7 with one central node connected to seven leaves: if each of seven unit disks touches a common unit disk, some two of the seven disks must touch each other. Therefore, unit disk graphs cannot contain an induced K_1,7 subgraph.

Applications

Beginning with the work of Huson & 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.^[1]

Computational complexity

It is NP-hard (more specifically, complete for the existential theory of the reals) to determine whether a graph, given without geometry, can be represented as a unit disk graph.^[2] Additionally, it is provably impossible in polynomial time to output explicit coordinates of a unit disk graph representation: there exist unit disk graphs that require exponentially many bits of precision in any such representation.^[3]

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,^[4] and the maximum clique problem can be solved exactly for these graphs in polynomial time, given a disk representation.^[5] More strongly, if a graph is given as input, it is possible in polynomial time to produce either a maximum clique or a proof that the graph is not a unit disk graph.^[6]

When a given vertex set forms a subset of a triangular lattice, a necessary and sufficient condition for the perfectness of a unit graph is known.^[7] For the perfect graphs, a number of NP-complete optimization problems (graph coloring problem, maximum clique problem, and maximum independent set problem) are polynomially solvable.

Notes

^ See, e.g., Dall & Christensen (2002).
^ Breu & Kirkpatrick (1998); Kang & Müller (2011).
^ McDiarmid & Mueller (2011).
^ Marathe et al. (1994); Matsui (2000).
^ Clark, Colbourn & Johnson (1990).
^ Raghavan & Spinrad (2003).
^ Miyamoto & Matsui (2005).

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, doi:10.1103/PhysRevE.66.016121 .
Huson, Mark L.; Sen, Arunabha (1995), "Broadcast scheduling algorithms for radio networks", Military Communications Conference, IEEE MILCOM '95, 2, pp. 647–651, doi:10.1109/MILCOM.1995.483546, ISBN 0-7803-2489-7 .
Kang, Ross J.; Müller, Tobias (2011), "Sphere and dot product representations of graphs", Proceedings of the Twenty-Seventh Annual Symposium on Computational Geometry (SCG'11), June 13–15, 2011, Paris, France, pp. 308–314 .
Marathe, Madhav V.; Breu, Heinz; Hunt, III, Harry B.; 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, Lecture Notes in Computer Science 1763: 194–200, doi:10.1007/978-3-540-46515-7_16, ISBN 978-3-540-67181-7 .
McDiarmid, Colin; Mueller, Tobias (2011), Integer realizations of disk and segment graphs, arXiv:1111.2931
Miyamoto, Yuichiro; Matsui, Tomomi (2005), "Perfectness and Imperfectness of the kth Power of Lattice Graphs", Lecture Notes in Computer Science, Lecture Notes in Computer Science 3521: 233–242, doi:10.1007/11496199_26, ISBN 978-3-540-26224-4 .
Raghavan, Vijay; Spinrad, Jeremy (2003), "Robust algorithms for restricted domains", Journal of Algorithms 48 (1): 160–172, doi:10.1016/S0196-6774(03)00048-8, MR 2006100 .