In
geometric graph theory
Geometric graph theory in the broader sense is a large and amorphous subfield of graph theory, concerned with graphs defined by geometric means. In a stricter sense, geometric graph theory studies combinatorial and geometric properties of geome ...
, a unit disk graph is the
intersection graph
In graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph can be represented as an intersection graph, but some important special classes of graphs can be defined by the types o ...
of a family of
unit disks in the
Euclidean plane. That is, it is a graph with one vertex for each disk in the family, and with an edge between two vertices whenever the corresponding vertices lie within a unit distance of each other.
They are commonly formed from a
Poisson point process
In probability, statistics and related fields, a Poisson point process is a type of random mathematical object that consists of points randomly located on a mathematical space with the essential feature that the points occur independently of one ...
, making them a simple example of a random structure.
Definitions
There are several possible definitions of the unit disk graph, equivalent to each other up to a choice of scale factor:
* Unit disk graphs are the graph formed from a collection of points in the Euclidean plane, with a vertex for each point and an edge connecting each pair of points whose distance is below a fixed threshold.
* Unit disk graphs are the
intersection graph
In graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph can be represented as an intersection graph, but some important special classes of graphs can be defined by the types o ...
s of equal-radius circles, or of equal-radius disks. These graphs have a vertex for each circle or disk, and an edge connecting each pair of circles or disks that have a nonempty intersection.
* Unit disk graphs may be formed in a different way from a collection of equal-radius circles, by connecting two circles with an edge whenever one circle contains the center of the other circle.
Properties
Every
induced subgraph
In the mathematical field of graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and ''all'' of the edges (from the original graph) connecting pairs of vertices in that subset.
Defini ...
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
A star is an astronomical object comprising a luminous spheroid of plasma (physics), plasma held together by its gravity. The List of nearest stars and brown dwarfs, nearest star to Earth is the Sun. Many other stars are visible to the naked ...
with one central node connected to six leaves: if each of six unit disks touches a common unit disk, some two of the six disks must touch each other. Therefore, unit disk graphs cannot contain an induced
subgraph. Infinitely many other forbidden induced subgraphs are known.
The number of unit disk graphs on
labeled vertices is within an exponential factor of
. This rapid growth implies that unit disk graphs do not have bounded
twin-width The twin-width of an undirected graph is a natural number associated with the graph, used to study the parameterized complexity of graph algorithms. Intuitively, it measures how similar the graph is to a cograph, a type of graph that can be reduced ...
.
Applications
Beginning with the work of , unit disk graphs have been used in
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
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 antenna
In radio communication, an omnidirectional antenna is a class of antenna which radiates equal radio power in all directions perpendicular to an axis (azimuthal directions), with power varying with angle to the axis ( elevation angle), declining ...
s. Node locations are modelled as Euclidean points, and the area within which a signal from one node can be received by another node is modelled 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 centres, have also been used as a model of
percolation
Percolation (from Latin ''percolare'', "to filter" or "trickle through"), in physics, chemistry and materials science, refers to the movement and filtering of fluids through porous materials.
It is described by Darcy's law.
Broader applicatio ...
and various other phenomena.
Computational complexity
If one is given a collection of unit disks (or their centres) in a space of any fixed dimension, it is possible to construct the corresponding unit disk graph in
linear time, by rounding the centres to nearby
integer grid points, using a
hash table
In computing, a hash table, also known as hash map, is a data structure that implements an associative array or dictionary. It is an abstract data type that maps keys to values. A hash table uses a hash function to compute an ''index'', ...
to find all pairs of centres within constant distance of each other, and filtering the resulting list of pairs for the ones whose circles intersect. The ratio of the number of pairs considered by this algorithm to the number of edges in the eventual graph is a constant, giving the linear time bound. However, this constant
grows exponentially
Exponential growth is a process that increases quantity over time. It occurs when the instantaneous rate of change (that is, the derivative) of a quantity with respect to time is proportional to the quantity itself. Described as a function, a q ...
as a function of the dimension.
It is
NP-hard (more specifically, complete for the
existential theory of the reals In mathematical logic, computational complexity theory, and computer science, the existential theory of the reals is the set of all true sentences of the form
\exists X_1 \cdots \exists X_n \, F(X_1,\dots, X_n),
where the variables X_i are interpre ...
) to determine whether a graph, given without geometry, can be represented as a unit disk graph. Additionally, it is 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.
However, many important and difficult graph optimization problems such as
maximum independent set
In graph theory, an independent set, stable set, coclique or anticlique is a set of vertices in a graph, no two of which are adjacent. That is, it is a set S of vertices such that for every two vertices in S, there is no edge connecting the tw ...
,
graph coloring, and minimum
dominating set
In graph theory, a dominating set for a graph is a subset of its vertices, such that any vertex of is either in , or has a neighbor in . The domination number is the number of vertices in a smallest dominating set for .
The dominating set ...
can be
approximated efficiently by using the geometric structure of these graphs, and the
maximum clique problem
In computer science, the clique problem is the computational problem of finding cliques (subsets of vertices, all adjacent to each other, also called complete subgraphs) in a graph. It has several different formulations depending on which cli ...
can be solved exactly for these graphs in polynomial time, given a disk representation.
[.] Even if a disk representation is not known, and an abstract 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, and to 3-approximate the optimum coloring by using a
greedy coloring
In the study of graph coloring problems in mathematics and computer science, a greedy coloring or sequential coloring is a coloring of the vertices of a graph formed by a greedy algorithm that considers the vertices of the graph in sequence an ...
algorithm.
See also
*
Barrier resilience, an algorithmic problem of breaking cycles in unit disk graphs
*
Indifference graph
In graph theory, a branch of mathematics, an indifference graph is an undirected graph constructed by assigning a real number to each vertex and connecting two vertices by an edge when their numbers are within one unit of each other.. Indifference ...
, a one-dimensional analogue of the unit disk graphs
*
Penny graph
In geometric graph theory, a penny graph is a contact graph of unit circles. It is formed from a collection of unit circles that do not cross each other, by creating a vertex for each circle and an edge for every pair of tangent circles. The circ ...
, the unit disk graphs for which the disks can be tangent but not overlap (
contact graph
In the mathematical area of graph theory, a contact graph or tangency graph is a graph whose vertices are represented by geometric objects (e.g. curves, line segments, or polygons), and whose edges correspond to two objects touching (but not cro ...
)
*
Coin graph, the contact graph of (not necessarily unit-sized) disks
*
Vietoris–Rips complex
In topology, the Vietoris–Rips complex, also called the Vietoris complex or Rips complex, is a way of forming a topological space from distances in a set of points. It is an abstract simplicial complex that can be defined from any metric space ...
, a generalization of the unit disk graph that constructs higher-order topological spaces from unit distances in a metric space
*
Unit distance graph
In mathematics, particularly geometric graph theory, a unit distance graph is a graph formed from a collection of points in the Euclidean plane by connecting two points whenever the distance between them is exactly one. To distinguish these gra ...
, a graph formed by connecting points that are at distance exactly one rather than (as here) at most a given threshold
Notes
References
*
*.
*
* .
* .
* .
*
*.
* .
*.
* .
* .
*
*
*{{citation
, last1 = Raghavan , first1 = Vijay
, last2 = Spinrad , first2 = Jeremy
, doi = 10.1016/S0196-6774(03)00048-8
, issue = 1
, journal = Journal of Algorithms
, mr = 2006100
, pages = 160–172
, title = Robust algorithms for restricted domains
, volume = 48
, year = 2003.
NP-complete problems
Intersection classes of graphs
Geometric graphs