HOME

TheInfoList



OR:

In mathematics, particularly geometric graph theory, a unit distance graph is a
graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discre ...
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 graphs from a broader definition that allows some non-adjacent pairs of vertices to be at distance one, they may also be called strict unit distance graphs or faithful unit distance graphs. As a hereditary family of graphs, they can be characterized by forbidden induced subgraphs. The unit distance graphs include the cactus graphs, the matchstick graphs and penny graphs, and the hypercube graphs. The generalized Petersen graphs are non-strict unit distance graphs. An unsolved problem of Paul Erdős asks how many edges a unit distance graph on n vertices can have. The best known lower bound is slightly above linear in n—far from the
upper bound In mathematics, particularly in order theory, an upper bound or majorant of a subset of some preordered set is an element of that is greater than or equal to every element of . Dually, a lower bound or minorant of is defined to be an elem ...
, proportional to n^. The number of colors required to
color Color (American English) or colour (British English) is the visual perceptual property deriving from the spectrum of light interacting with the photoreceptor cells of the eyes. Color categories and physical specifications of color are assoc ...
unit distance graphs is also unknown (the
Hadwiger–Nelson problem In geometric graph theory, the Hadwiger–Nelson problem, named after Hugo Hadwiger and Edward Nelson, asks for the minimum number of colors required to color the plane such that no two points at distance 1 from each other have the same color ...
): some unit distance graphs require five colors, and every unit distance graph can be colored with seven colors. For every algebraic number there is a unit distance graph with two vertices that must be that distance apart. According to the Beckman–Quarles theorem, the only plane transformations that preserve all unit distance graphs are the isometries. It is possible to construct a unit distance graph efficiently, given its points. Finding all unit distances has applications in
pattern matching In computer science, pattern matching is the act of checking a given sequence of tokens for the presence of the constituents of some pattern. In contrast to pattern recognition, the match usually has to be exact: "either it will or will not be ...
, where it can be a first step in finding congruent copies of larger patterns. However, determining whether a given graph can be represented as a unit distance graph is NP-hard, and more specifically complete for the existential theory of the reals.


Definition

The unit distance graph for a set of points in the plane is the undirected graph having those points as its vertices, with an edge between two vertices whenever their Euclidean distance is exactly one. An abstract graph is said to be a unit distance graph if it is possible to find distinct locations in the plane for its vertices, so that its edges have unit length and so that all non-adjacent pairs of vertices have non-unit distances. When this is possible, the abstract graph is isomorphic to the unit distance graph of the chosen locations. Alternatively, some sources use a broader definition, allowing non-adjacent pairs of vertices to be at unit distance. The resulting graphs are the subgraphs of the unit distance graphs (as defined here). Where the terminology may be ambiguous, the graphs in which non-edges must be a non-unit distance apart may be called strict unit distance graphs or faithful unit distance graphs. The subgraphs of unit distance graphs are equivalently the graphs that can be drawn in the plane using only one edge length. For brevity, this article refers to these as "non-strict unit distance graphs". Unit distance graphs should not be confused with unit disk graphs, which connect pairs of points when their distance is less than or equal to one, and are frequently used to model wireless communication networks.


Examples

The
complete graph In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices ...
on two vertices is a unit distance graph, as is the complete graph on three vertices (the triangle graph), but not the complete graph on four vertices. Generalizing the triangle graph, every cycle graph is a unit distance graph, realized by a regular polygon. Two finite unit distance graphs, connected at a single shared vertex, yield another unit distance graph, as one can be rotated with respect to the other to avoid undesired additional unit distances. By thus connecting graphs, every finite
tree In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are ...
or cactus graph may be realized as a unit distance graph. Any
Cartesian product In mathematics, specifically set theory, the Cartesian product of two sets ''A'' and ''B'', denoted ''A''×''B'', is the set of all ordered pairs where ''a'' is in ''A'' and ''b'' is in ''B''. In terms of set-builder notation, that is : A\ ...
of unit distance graphs produces another unit distance graph; however, the same is not true for some other common graph products. For instance, the strong product of graphs, applied to any two non-empty graphs, produces complete subgraphs with four vertices, which are not unit distance graphs. The Cartesian products of
path graph In the mathematical field of graph theory, a path graph or linear graph is a graph whose vertices can be listed in the order such that the edges are where . Equivalently, a path with at least two vertices is connected and has two terminal ...
s form grid graphs of any dimension, the Cartesian products of the complete graph on two vertices are the hypercube graphs, and the Cartesian products of triangle graphs are the Hamming graphs H(d,3). Other specific graphs that are unit distance graphs include the
Petersen graph In the mathematics, mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertex (graph theory), vertices and 15 edge (graph theory), edges. It is a small graph that serves as a useful example and counterexample for ...
, the
Heawood graph Heawood is a surname. Notable people with the surname include: * Jonathan Heawood, British journalist * Percy John Heawood (1861–1955), British mathematician ** Heawood conjecture ** Heawood graph ** Heawood number See also *Heywood (surname) He ...
, the
wheel graph A wheel is a circular component that is intended to rotate on an axle bearing. The wheel is one of the key components of the wheel and axle which is one of the six simple machines. Wheels, in conjunction with axles, allow heavy objects to be ...
W_7 (the only wheel graph that is a unit distance graph), and the
Moser spindle In graph theory, a branch of mathematics, the Moser spindle (also called the Mosers' spindle or Moser graph) is an undirected graph, named after mathematicians Leo Moser and his brother William, with seven vertices and eleven edges. It is a unit ...
and Golomb graph (small 4-
chromatic Diatonic and chromatic are terms in music theory that are most often used to characterize scales, and are also applied to musical instruments, intervals, chords, notes, musical styles, and kinds of harmony. They are very often used as a ...
unit distance graphs). All generalized Petersen graphs, such as the
Möbius–Kantor graph In the mathematical field of graph theory, the Möbius–Kantor graph is a symmetric bipartite cubic graph with 16 vertices and 24 edges named after August Ferdinand Möbius and Seligmann Kantor. It can be defined as the generalized Petersen grap ...
depicted, are non-strict unit distance graphs.
Matchstick graph In geometric graph theory, a branch of mathematics, a matchstick graph is a graph that can be drawn in the plane in such a way that its edges are line segments with length one that do not cross each other. That is, it is a graph that has an em ...
s are a special case of unit distance graphs, in which no edges cross. Every matchstick graph is a
planar graph In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cro ...
, but some otherwise-planar unit distance graphs (such as the Moser spindle) have a crossing in every representation as a unit distance graph. Additionally, in the context of unit distance graphs, the term 'planar' should be used with care, as some authors use it to refer to the plane in which the unit distances are defined, rather than to a prohibition on crossings. The penny graphs are an even more special case of unit distance and matchstick graphs, in which every non-adjacent pair of vertices are more than one unit apart.


Properties


Number of edges

posed the problem of estimating how many pairs of points in a set of n points could be at unit distance from each other. In graph-theoretic terms, the question asks how dense a unit distance graph can be, and Erdős's publication on this question was one of the first works in
extremal graph theory Extremal graph theory is a branch of combinatorics, itself an area of mathematics, that lies at the intersection of extremal combinatorics and graph theory. In essence, extremal graph theory studies how global properties of a graph influence loc ...
. The hypercube graphs and Hamming graphs provide a lower bound on the number of unit distances, proportional to n\log n. By considering points in a square grid with carefully chosen spacing, Erdős found an improved lower bound of the form n^ for a constant c, and offered $500 for a proof of whether the number of unit distances can also be bounded above by a function of this form. The best known upper bound for this problem is \sqrt approx 1.936n^. This bound can be viewed as counting incidences between points and unit circles, and is closely related to the
crossing number inequality In the mathematics of graph drawing, the crossing number inequality or crossing lemma gives a lower bound on the Crossing number (graph theory), minimum number of crossings of a given Graph (discrete mathematics), graph, as a function of the number ...
and to the
Szemerédi–Trotter theorem The Szemerédi–Trotter theorem is a mathematical result in the field of Discrete geometry. It asserts that given points and lines in the Euclidean plane, the number of incidences (''i.e.'', the number of point-line pairs, such that the point ...
on incidences between points and lines. For small values of n (up to 14, ), the exact maximum number of possible edges is known. For n=2,3,4,\dots these numbers of edges are:


Forbidden subgraphs

If a given graph G is not a non-strict unit distance graph, neither is any supergraph H of G. A similar idea works for strict unit distance graphs, but using the concept of an
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 ...
, a subgraph formed from all edges between the pairs of vertices in a given subset of vertices. If G is not a strict unit distance graph, then neither is any other H that has G as an induced subgraph. Because of these relations between whether a subgraph or its supergraph is a unit distance graph, it is possible to describe unit distance graphs by their forbidden subgraphs. These are the minimal graphs that are not unit distance graphs of the given type. They can be used to determine whether a given graph G is a unit distance graph, of either type. G is a non-strict unit distance graph, if and only if G is not a supergraph of a forbidden graph for the non-strict unit distance graphs. G is a strict unit distance graph, if and only if G is not an induced supergraph of a forbidden graph for the strict unit distance graphs. For both the non-strict and strict unit distance graphs, the forbidden graphs include both the complete graph K_4 and the
complete bipartite graph In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set..Electronic edition page 17. Graph theory ...
K_. For K_, wherever the vertices on the two-vertex side of this graph are placed, there are at most two positions at unit distance from them to place the other three vertices, so it is impossible to place all three vertices at distinct points. These are the only two forbidden graphs for the non-strict unit distance graphs on up to five vertices; there are six forbidden graphs on up to seven vertices and 74 on graphs up to nine vertices. Because gluing two unit distance graphs (or subgraphs thereof) at a vertex produce strict (respectively non-strict) unit distance graphs, every forbidden graph is a
biconnected graph In graph theory, a biconnected graph is a connected and "nonseparable" graph, meaning that if any one vertex were to be removed, the graph will remain connected. Therefore a biconnected graph has no articulation vertices. The property of being ...
, one that cannot be formed by this gluing process. The
wheel graph A wheel is a circular component that is intended to rotate on an axle bearing. The wheel is one of the key components of the wheel and axle which is one of the six simple machines. Wheels, in conjunction with axles, allow heavy objects to be ...
W_7 can be realized as a strict unit distance graph with six of its vertices forming a unit
regular hexagon In geometry, a hexagon (from Greek , , meaning "six", and , , meaning "corner, angle") is a six-sided polygon. The total of the internal angles of any simple (non-self-intersecting) hexagon is 720°. Regular hexagon A '' regular hexagon'' has ...
and the seventh at the center of the hexagon. Removing one of the edges from the center vertex produces a subgraph that still has unit-length edges, but which is not a strict unit distance graph. The regular-hexagon placement of its vertices is the only one way (
up to Two mathematical objects ''a'' and ''b'' are called equal up to an equivalence relation ''R'' * if ''a'' and ''b'' are related by ''R'', that is, * if ''aRb'' holds, that is, * if the equivalence classes of ''a'' and ''b'' with respect to ''R'' a ...
congruence) to place the vertices at distinct locations such that adjacent vertices are a unit distance apart, and this placement also puts the two endpoints of the missing edge at unit distance. Thus, it is a forbidden graph for the strict unit distance graphs, but not one of the six forbidden graphs for the non-strict unit distance graphs. Other examples of graphs that are non-strict unit distance graphs but not strict unit distance graphs include the graph formed by removing an outer edge from W_7, and the six-vertex graph formed from a
triangular prism In geometry, a triangular prism is a three-sided prism; it is a polyhedron made of a triangular base, a translated copy, and 3 faces joining corresponding sides. A right triangular prism has rectangular sides, otherwise it is ''oblique''. ...
by removing an edge from one of its triangles.


Algebraic numbers and rigidity

For every algebraic number \alpha, it is possible to construct a unit distance graph G in which some pair of vertices are at distance \alpha in all unit distance representations of G. This result implies a finite version of the Beckman–Quarles theorem: for any two points p and q at distance \alpha from each other, there exists a finite rigid unit distance graph containing p and q such that any transformation of the plane that preserves the unit distances in this graph also preserves the distance between p and q. The full Beckman–Quarles theorem states that the only transformations of the Euclidean plane (or a higher-dimensional Euclidean space) that preserve unit distances are the isometries. Equivalently, for the infinite unit distance graph generated by all the points in the plane, all
graph automorphism In the mathematical field of graph theory, an automorphism of a graph is a form of symmetry in which the graph is mapped onto itself while preserving the edge–vertex connectivity. Formally, an automorphism of a graph is a permutation of the ...
s preserve all of the distances in the plane, not just the unit distances. If \alpha is an algebraic number of modulus 1 that is not a
root of unity In mathematics, a root of unity, occasionally called a de Moivre number, is any complex number that yields 1 when raised to some positive integer power . Roots of unity are used in many branches of mathematics, and are especially important i ...
, then the integer combinations of powers of \alpha form a finitely generated subgroup of the
additive group An additive group is a group of which the group operation is to be thought of as ''addition'' in some sense. It is usually abelian, and typically written using the symbol + for its binary operation. This terminology is widely used with structure ...
of
complex number In mathematics, a complex number is an element of a number system that extends the real numbers with a specific element denoted , called the imaginary unit and satisfying the equation i^= -1; every complex number can be expressed in the for ...
s whose unit distance graph has infinite
degree Degree may refer to: As a unit of measurement * Degree (angle), a unit of angle measurement ** Degree of geographical latitude ** Degree of geographical longitude * Degree symbol (°), a notation used in science, engineering, and mathemati ...
. For instance, \alpha can be chosen as one of the two complex roots of the polynomial z^4-z^3-z^2-z+1, producing an infinite-degree unit distance graph with four generators.


Coloring

The
Hadwiger–Nelson problem In geometric graph theory, the Hadwiger–Nelson problem, named after Hugo Hadwiger and Edward Nelson, asks for the minimum number of colors required to color the plane such that no two points at distance 1 from each other have the same color ...
concerns the
chromatic number 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 o ...
of unit distance graphs, and more specifically of the infinite unit distance graph formed from all points of the Euclidean plane. By the de Bruijn–Erdős theorem, which assumes the
axiom of choice In mathematics, the axiom of choice, or AC, is an axiom of set theory equivalent to the statement that ''a Cartesian product of a collection of non-empty sets is non-empty''. Informally put, the axiom of choice says that given any collection ...
, this is equivalent to asking for the largest chromatic number of a finite unit distance graph. There exist unit distance graphs requiring five colors in any proper coloring, and all unit distance graphs can be colored with at most seven colors. Answering another question of Paul Erdős, it is possible for triangle-free unit distance graphs to require four colors.


Enumeration

The number of strict unit distance graphs on n\ge 4 labeled vertices is at most \binom=O\left(2^\right), as expressed using big O notation and little o notation.


Generalization to higher dimensions

The definition of a unit distance graph may naturally be generalized to any higher-dimensional
Euclidean space Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, that is, in Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are Euclidean sp ...
. In three dimensions, unit distance graphs of n points have at most n^\beta(n) edges, where \beta is a very slowly growing function related to the inverse
Ackermann function In computability theory, the Ackermann function, named after Wilhelm Ackermann, is one of the simplest and earliest-discovered examples of a total computable function that is not primitive recursive. All primitive recursive functions are total ...
. This result leads to a similar bound on the number of edges of three-dimensional
relative neighborhood graph In computational geometry, the relative neighborhood graph (RNG) is an undirected graph defined on a set of points in the Euclidean plane by connecting two points p and q by an edge whenever there does not exist a third point r that is closer to b ...
s. In four or more dimensions, any
complete bipartite graph In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set..Electronic edition page 17. Graph theory ...
is a unit distance graph, realized by placing the points on two perpendicular circles with a common center, so unit distance graphs can be
dense graph In mathematics, a dense graph is a graph in which the number of edges is close to the maximal number of edges (where every pair of vertices is connected by one edge). The opposite, a graph with only a few edges, is a sparse graph. The distinctio ...
s. The enumeration formulas for unit distance graphs generalize to higher dimensions, and shows that in dimensions four or more the number of strict unit distance graphs is much larger than the number of subgraphs of unit distance graphs. Any finite graph may be embedded as a unit distance graph in a sufficiently high dimension. Some graphs may need very different dimensions for embeddings as non-strict unit distance graphs and as strict unit distance graphs. For instance the 2n-vertex
crown graph In graph theory, a branch of mathematics, a crown graph on vertices is an undirected graph with two sets of vertices and and with an edge from to whenever . The crown graph can be viewed as a complete bipartite graph from which the edges ...
may be embedded in four dimensions as a non-strict unit distance graph (that is, so that all its edges have unit length). However, it requires at least n-2 dimensions to be embedded as a strict unit distance graph, so that its edges are the only unit-distance pairs. The dimension needed to realize any given graph as a strict unit graph is at most twice its maximum degree.


Computational complexity

Constructing a unit distance graph from its points is an important step for other algorithms for finding congruent copies of some pattern in a larger point set. These algorithms use this construction to search for candidate positions where one of the distances in the pattern is present, and then use other methods to test the rest of the pattern for each candidate. A method of can be applied to this problem, yielding an algorithm for finding a planar point set's unit distance graph in time n^2^ where \log^* is the slowly growing
iterated logarithm In computer science, the iterated logarithm of n, written  n (usually read "log star"), is the number of times the logarithm function must be iteratively applied before the result is less than or equal to 1. The simplest formal definition i ...
function.; see also for a closely related algorithm for listing point–line incidences in time O(n^). It is NP-hard—and more specifically, complete for the existential theory of the reals—to test whether a given graph is a (strict or non-strict) unit distance graph in the plane. It is also
NP-complete In computational complexity theory, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryin ...
to determine whether a planar unit distance graph has a
Hamiltonian cycle In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle that visits each vertex ...
, even when the graph's vertices all have known integer coordinates.


References


Notes


Sources

* * * * * * * * *, as cited by * * * * *, as cited by *; see in particula
p. 475
* * * * * * * * * * * * * * * * * * * * * * * *


External links

* *{{mathworld, urlname=Unit-DistanceGraph, title=Unit-Distance Graph, mode=cs2 Geometric graphs