Unit disk graph

From Wikipedia, the free encyclopedia

A collection of unit circles and the corresponding unit disk graph.
A collection of unit circles and the corresponding 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.

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

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 & 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]

It is NP-hard to determine whether a graph, given without geometry, can be represented as a unit disk graph.[2] 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,[3] and the maximum clique problem can be solved exactly for these graphs in polynomial time, given a disk representation.[4]

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.[5] 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.

[edit] See also

  • Vietoris–Rips complex, a generalization of the unit disk graph that constructs higher-order topological spaces from unit distances in a metric space

[edit] Notes

  1. ^ See, e.g., Dall & Christensen (2002).
  2. ^ Breu & Kirkpatrick (1998).
  3. ^ Marathe et al. (1994); Matsui (2000).
  4. ^ Clark, Colbourn & Johnson (1990).
  5. ^ Miyamoto & Matsui (2005).

[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 
  • 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 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