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

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 ...

K_

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

K_

subgraph. Infinitely many other forbidden induced subgraphs are known. The number of unit disk graphs on

n

labeled vertices is within an exponential factor of

n^

. 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.

Notes

References