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

of a family of

unit disk In mathematics, the open unit disk (or disc) around ''P'' (where ''P'' is a given point in the plane), is the set of points whose distance from ''P'' is less than 1: :D_1(P) = \.\, The closed unit disk around ''P'' is the set of points whose ...

s in the

Euclidean plane In mathematics, the Euclidean plane is a Euclidean space of dimension two. That is, a geometric setting in which two real quantities are required to determine the position of each point ( element of the plane), which includes affine notions ...

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

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 held together by its gravity. The nearest star to Earth is the Sun. Many other stars are visible to the naked eye at night, but their immense distances from Earth make ...

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.

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 practical disciplines (includin ...

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 Base station (or base radio station) is – according to the International Telecommunication Union's (ITU) Radio Regulations (RR) – a " land station in the land mobile service." The term is used in the context of mobile telephony, wireless c ...

. 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), declinin ...

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 In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by t ...

, 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 In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...

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

graph coloring In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices ...

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

algorithm.

Notes

References