Unit distance graph

Last updated

A unit distance graph with 16 vertices and 40 edges Unit distance 16 40.svg
A unit distance graph with 16 vertices and 40 edges

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

Contents

An unsolved problem of Paul Erdős asks how many edges a unit distance graph on vertices can have. The best known lower bound is slightly above linear in —far from the upper bound, proportional to . The number of colors required to color unit distance graphs is also unknown (the Hadwiger–Nelson problem): 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, 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

Petersen graph, unit distance.svg
The Petersen graph as a unit distance graph [1]
Mobius-Kantor unit distance.svg
The Möbius–Kantor graph as a subgraph of a unit distance graph

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). [2] 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 [3] or faithful unit distance graphs. [2] The subgraphs of unit distance graphs are equivalently the graphs that can be drawn in the plane using only one edge length. [4] 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. [5]

Examples

The complete graph 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. [3] Generalizing the triangle graph, every cycle graph is a unit distance graph, realized by a regular polygon. [4] 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. [6] By thus connecting graphs, every finite tree or cactus graph may be realized as a unit distance graph. [7]

Hypercubestar.svg
The hypercube graph has 16 vertices and 32 unit distances
Hamming33UnitDistance.gif
The Hamming graph has 27 vertices and 81 unit distances

Any Cartesian product 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 graphs form grid graphs of any dimension, the Cartesian products of the complete graph on two vertices are the hypercube graphs, [8] and the Cartesian products of triangle graphs are the Hamming graphs . [9]

Other specific graphs that are unit distance graphs include the Petersen graph, [10] the Heawood graph, [11] the wheel graph (the only wheel graph that is a unit distance graph), [3] and the Moser spindle and Golomb graph (small 4-chromatic unit distance graphs). [12] All generalized Petersen graphs, such as the Möbius–Kantor graph depicted, are non-strict unit distance graphs. [13]

Matchstick graphs are a special case of unit distance graphs, in which no edges cross. Every matchstick graph is a planar graph, [14] 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. [3] 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. [14]

Properties

Number of edges

Unsolved problem in mathematics:

How many unit distances can be determined by a set of points?

PaulErdős  ( 1946 ) posed the problem of estimating how many pairs of points in a set of 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. [15] The hypercube graphs and Hamming graphs provide a lower bound on the number of unit distances, proportional to By considering points in a square grid with carefully chosen spacing, Erdős found an improved lower bound of the form

for a constant , and offered $500 for a proof of whether the number of unit distances can also be bounded above by a function of this form. [16] The best known upper bound for this problem is

This bound can be viewed as counting incidences between points and unit circles, and is closely related to the crossing number inequality and to the Szemerédi–Trotter theorem on incidences between points and lines. [17]

For small values of (up to 14, as of 2022), the exact maximum number of possible edges is known. For these numbers of edges are: [18]

1, 3, 5, 7, 9, 12, 14, 18, 20, 23, 27, 30, 33, ... (sequence A186705 in the OEIS)

Forbidden subgraphs

If a given graph is not a non-strict unit distance graph, neither is any supergraph of . A similar idea works for strict unit distance graphs, but using the concept of an induced subgraph, a subgraph formed from all edges between the pairs of vertices in a given subset of vertices. If is not a strict unit distance graph, then neither is any other that has 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 is a unit distance graph, of either type. is a non-strict unit distance graph, if and only if is not a supergraph of a forbidden graph for the non-strict unit distance graphs. is a strict unit distance graph, if and only if is not an induced supergraph of a forbidden graph for the strict unit distance graphs. [8]

For both the non-strict and strict unit distance graphs, the forbidden graphs include both the complete graph and the complete bipartite graph . For , 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. [8] 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 [6] 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, one that cannot be formed by this gluing process. [19]

The wheel graph can be realized as a strict unit distance graph with six of its vertices forming a unit regular hexagon 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 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, [20] 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 , and the six-vertex graph formed from a triangular prism by removing an edge from one of its triangles. [19]

Algebraic numbers and rigidity

For every algebraic number , it is possible to construct a unit distance graph in which some pair of vertices are at distance in all unit distance representations of . [21] This result implies a finite version of the Beckman–Quarles theorem: for any two points and at distance from each other, there exists a finite rigid unit distance graph containing and such that any transformation of the plane that preserves the unit distances in this graph also preserves the distance between and . [22] 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 automorphisms preserve all of the distances in the plane, not just the unit distances. [23]

If is an algebraic number of modulus 1 that is not a root of unity, then the integer combinations of powers of form a finitely generated subgroup of the additive group of complex numbers whose unit distance graph has infinite degree. For instance, can be chosen as one of the two complex roots of the polynomial , producing an infinite-degree unit distance graph with four generators. [24]

Coloring

Unsolved problem in mathematics:

What is the largest possible chromatic number of a unit distance graph?

The Hadwiger–Nelson problem concerns the chromatic number 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, 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, [25] and all unit distance graphs can be colored with at most seven colors. [26]

A seven-coloring of the infinite unit distance graph formed from all points of the plane, and the four-chromatic Moser spindle embedded as a unit distance graph Hadwiger-Nelson.svg
A seven-coloring of the infinite unit distance graph formed from all points of the plane, and the four-chromatic Moser spindle embedded as a unit distance graph

Answering another question of Paul Erdős, it is possible for triangle-free unit distance graphs to require four colors. [27]

Enumeration

The number of strict unit distance graphs on labeled vertices is at most [2]

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. In three dimensions, unit distance graphs of points have at most edges, where is a very slowly growing function related to the inverse Ackermann function. [28] This result leads to a similar bound on the number of edges of three-dimensional relative neighborhood graphs. [29] In four or more dimensions, any complete bipartite graph 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 graphs. [7] 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. [2]

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 -vertex crown graph 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 dimensions to be embedded as a strict unit distance graph, so that its edges are the only unit-distance pairs. [30] The dimension needed to realize any given graph as a strict unit graph is at most twice its maximum degree. [31]

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. [32] A method of Matoušek (1993) can be applied to this problem, [32] yielding an algorithm for finding a planar point set's unit distance graph in time where is the slowly growing iterated logarithm function. [33]

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. [34] It is also NP-complete to determine whether a planar unit distance graph has a Hamiltonian cycle, even when the graph's vertices all have known integer coordinates. [35]

Related Research Articles

<span class="mw-page-title-main">Petersen graph</span> Cubic graph with 10 vertices and 15 edges

In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is named after Julius Petersen, who in 1898 constructed it to be the smallest bridgeless cubic graph with no three-edge-coloring.

<span class="mw-page-title-main">Component (graph theory)</span> Maximal subgraph whose vertices can reach each other

In graph theory, a component of an undirected graph is a connected subgraph that is not part of any larger connected subgraph. The components of any graph partition its vertices into disjoint sets, and are the induced subgraphs of those sets. A graph that is itself connected has exactly one component, consisting of the whole graph. Components are sometimes called connected components.

<span class="mw-page-title-main">Turán graph</span> Balanced complete multipartite graph

The Turán graph, denoted by , is a complete multipartite graph; it is formed by partitioning a set of vertices into subsets, with sizes as equal as possible, and then connecting two vertices by an edge if and only if they belong to different subsets. Where and are the quotient and remainder of dividing by , the graph is of the form , and the number of edges is

<span class="mw-page-title-main">Extremal graph theory</span>

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 local substructure. Results in extremal graph theory deal with quantitative connections between various graph properties, both global and local, and problems in extremal graph theory can often be formulated as optimization problems: how big or small a parameter of a graph can be, given some constraints that the graph has to satisfy? A graph that is an optimal solution to such an optimization problem is called an extremal graph, and extremal graphs are important objects of study in extremal graph theory.

<span class="mw-page-title-main">Perfect graph</span> Graph with tight clique-coloring relation

In graph theory, a perfect graph is a graph in which the chromatic number equals the size of the maximum clique, both in the graph itself and in every induced subgraph. In all graphs, the chromatic number is greater than or equal to the size of the maximum clique, but they can be far apart. A graph is perfect when these numbers are equal, and remain equal after the deletion of arbitrary subsets of vertices.

<span class="mw-page-title-main">Critical graph</span> Undirected graph

In graph theory, a critical graph is an undirected graph all of whose proper subgraphs have smaller chromatic number. In such a graph, every vertex or edge is a critical element, in the sense that its deletion would decrease the number of colors needed in a graph coloring of the given graph. The decrease in the number of colors cannot be by more than one.

<span class="mw-page-title-main">Edge coloring</span> Problem of coloring a graphs edges such that meeting edges do not match

In graph theory, a proper edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several different types of graph coloring. The edge-coloring problem asks whether it is possible to color the edges of a given graph using at most k different colors, for a given value of k, or with the fewest possible colors. The minimum required number of colors for the edges of a given graph is called the chromatic index of the graph. For example, the edges of the graph in the illustration can be colored by three colors but cannot be colored by two colors, so the graph shown has chromatic index three.

<span class="mw-page-title-main">Degree (graph theory)</span> Number of edges touching a vertex in a graph

In graph theory, the degree of a vertex of a graph is the number of edges that are incident to the vertex; in a multigraph, a loop contributes 2 to a vertex's degree, for the two ends of the edge. The degree of a vertex is denoted or . The maximum degree of a graph is denoted by , and is the maximum of 's vertices' degrees. The minimum degree of a graph is denoted by , and is the minimum of 's vertices' degrees. In the multigraph shown on the right, the maximum degree is 5 and the minimum degree is 0.

<span class="mw-page-title-main">Hadwiger conjecture (graph theory)</span> Unproven generalization of the four-color theorem

In graph theory, the Hadwiger conjecture states that if is loopless and has no minor then its chromatic number satisfies . It is known to be true for . The conjecture is a generalization of the four-color theorem and is considered to be one of the most important and challenging open problems in the field.

The arboricity of an undirected graph is the minimum number of forests into which its edges can be partitioned. Equivalently it is the minimum number of spanning forests needed to cover all the edges of the graph. The Nash-Williams theorem provides necessary and sufficient conditions for when a graph is k-arboric.

<span class="mw-page-title-main">Hadwiger–Nelson problem</span> Mathematical 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. The answer is unknown, but has been narrowed down to one of the numbers 5, 6 or 7. The correct value may depend on the choice of axioms for set theory.

<span class="mw-page-title-main">Unit disk graph</span> Intersection graph of unit disks in the plane

In geometric graph theory, a unit disk graph is the intersection graph 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.

<span class="mw-page-title-main">Triangle-free graph</span> Graph without triples of adjacent vertices

In the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with girth ≥ 4, graphs with no induced 3-cycle, or locally independent graphs.

<span class="mw-page-title-main">Grötzsch graph</span> Triangle-free graph requiring four colors

In the mathematical field of graph theory, the Grötzsch graph is a triangle-free graph with 11 vertices, 20 edges, chromatic number 4, and crossing number 5. It is named after German mathematician Herbert Grötzsch, who used it as an example in connection with his 1959 theorem that planar triangle-free graphs are 3-colorable.

<span class="mw-page-title-main">Moser spindle</span> Undirected unit-distance graph requiring four colors

In graph theory, a branch of mathematics, the Moser spindle is an undirected graph, named after mathematicians Leo Moser and his brother William, with seven vertices and eleven edges. It is a unit distance graph requiring four colors in any graph coloring, and its existence can be used to prove that the chromatic number of the plane is at least four.

In graph theory, a branch of mathematics, a crown graph on 2n vertices is an undirected graph with two sets of vertices {u1, u2, …, un} and {v1, v2, …, vn} and with an edge from ui to vj whenever ij.

In graph theory, the De Bruijn–Erdős theorem relates graph coloring of an infinite graph to the same problem on its finite subgraphs. It states that, when all finite subgraphs can be colored with colors, the same is true for the whole graph. The theorem was proved by Nicolaas Govert de Bruijn and Paul Erdős, after whom it is named.

<span class="mw-page-title-main">Degeneracy (graph theory)</span> Measurement of graph sparsity

In graph theory, a k-degenerate graph is an undirected graph in which every subgraph has a vertex of degree at most k: that is, some vertex in the subgraph touches k or fewer of the subgraph's edges. The degeneracy of a graph is the smallest value of k for which it is k-degenerate. The degeneracy of a graph is a measure of how sparse it is, and is within a constant factor of other sparsity measures such as the arboricity of a graph.

<span class="mw-page-title-main">Topological graph</span>

In mathematics, a topological graph is a representation of a graph in the plane, where the vertices of the graph are represented by distinct points and the edges by Jordan arcs joining the corresponding pairs of points. The points representing the vertices of a graph and the arcs representing its edges are called the vertices and the edges of the topological graph. It is usually assumed that any two edges of a topological graph cross a finite number of times, no edge passes through a vertex different from its endpoints, and no two edges touch each other. A topological graph is also called a drawing of a graph.

In graph theory, a branch of mathematics, the Erdős–Hajnal conjecture states that families of graphs defined by forbidden induced subgraphs have either large cliques or large independent sets. It is named for Paul Erdős and András Hajnal, who first posed it as an open problem in a paper from 1977.

References

Notes

Sources