Unit distance graph

As a hereditary family of graphs, they can be characterized by forbidden induced subgraphs.

An unsolved problem of Paul Erdős asks how many edges a unit distance graph on

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.

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.

Alternatively, some sources use a broader definition, allowing non-adjacent pairs of vertices to be at unit distance.

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

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.

[14] Paul Erdős (1946) posed the problem of estimating how many pairs of points in a set of

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.

By considering points in a square grid with carefully chosen spacing, Erdős found an improved lower bound of the form

, and offered $500 for a proof of whether the number of unit distances can also be bounded above by a function of this form.

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.

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.

, and the six-vertex graph formed from a triangular prism by removing an edge from one of its triangles.

from each other, there exists a finite rigid unit distance graph containing

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.

, producing an infinite-degree unit distance graph with four generators.

[24] 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.

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

The definition of a unit distance graph may naturally be generalized to any higher-dimensional Euclidean space.

[28] This result leads to a similar bound on the number of edges of three-dimensional relative neighborhood 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.

dimensions to be embedded as a strict unit distance graph, so that its edges are the only unit-distance pairs.

[31] 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.

[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