Unit distance graph

A unit distance graph with 16 vertices and 40 edges

In mathematics, and 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 by an edge whenever the distance between the two points is exactly one. To distinguish these graphs from the larger family of their subgraphs, they may 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 subgraphs of unit distance graphs.

It is unknown how many edges a unit distance graph on $n$ vertices can have; the lower bound is slightly superlinear and the upper bound (expressed in big O notation) is $O(n^{4/3})$. The number of colors required to color unit distance graphs is also unknown: 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. The only transformations of the plane that preserve all unit distance graphs are the isometries.

It is possible to construct a unit distance graph efficiently, given its points. 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 Petersen graph as a unit distance graph

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 given 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). In cases where the naming of these graphs might be ambiguous, the graphs in which non-edges are required to 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 with only one edge length.

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 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. If two finite unit distance graphs are connected at a single shared vertex, the result is again a unit distance graph, as one of the two graphs can be rotated with respect to the other to avoid undesired additional unit distances. By connecting graphs in this way, every tree and every cactus graph may be realized as a unit distance graph.

The hypercube graph $Q_{4}$ has 16 vertices and 32 unit distances

The Hamming graph $H(3,3)$ 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 other commonly-used graph products. 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, and the Cartesian products of triangle graphs are the Hamming graphs $H(d,3)$.

Matchstick graphs are a special case of unit distance graphs, in which no edges cross. Every matchstick graph is a planar graph, but some 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 graphs and matchstick graphs, in which every non-adjacent pair of vertices is at greater than unit distance from each other.

Other specific graphs that are unit distance graphs include the Petersen graph, the Heawood graph, the wheel graph $W_{7}$ (the only wheel graph that is a unit distance graph), and the Moser spindle and Golomb graph (small 4-chromatic unit distance graphs). All generalized Petersen graphs, such as the Möbius–Kantor graph depicted, are subgraphs of unit distance graphs.

Properties

Number of edges

See also: Erdős distinct distances problem

Unsolved problem in mathematics

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

More unsolved problems in mathematics

Paul Erdős (1946) posed the problem of estimating how many pairs of points in a set of $n$ points could be at unit distance from each other. This question can be phrased in graph theoretic terms as asking 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. 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^{1+c/\log \log n},$$ and offered a prize of $500 for determining whether or not the maximum number of unit distances can also be upper bounded by a function of this form. The best known upper bound for this problem is proportional to $$n^{4/3}.$$ This bound can also 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.

For small values of $n$, the exact maximum number of possible edges is known. For $n=2,3,4,\dots$ these numbers of edges are:

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

Forbidden subgraphs

Being a strict unit distance graph, or a subgraph of a unit distance graph, are hereditary properties: every induced subgraph of a graph of either type is a graph of the same type. Therefore, these properties can be described by forbidden subgraphs: a graph has one of these properties if and only if its induced subgraphs do not include any of the minimal counterexamples to the properties. As well as the complete graph $K_{4}$, these forbidden graphs include the complete bipartite graph $K_{2,3}$: wherever the vertices on the two-vertex side of this graph are placed, there are at most two positions at unit distance from them where the other three vertices could be placed. These are the only two forbidden graphs for the subgraphs of unit distance graphs on up to five vertices; there are six forbidden graphs on up to seven vertices and 74 forbidden graphs on up to nine vertices. Because graphs formed by gluing two smaller unit distance graphs (or subgraphs of unit distance graphs) at a vertex are themselves unit distance graphs, every forbidden graph is a biconnected graph, one that cannot be formed by this gluing process.

The wheel graph $W_{7}$ 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 unit distance graphs, but it is not one of the six forbidden graphs for the subgraphs of unit distance graphs.

Algebraic numbers and rigidity

Main article: Beckman–Quarles theorem

For every algebraic number A, it is possible to find a unit distance graph G in which some pair of vertices are at distance A 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 A, 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 preserves the distance between p and q. The full Beckman–Quarles theorem states that any transformation of the Euclidean plane (or a higher-dimensional space) that preserves unit distances must be a congruence; that is, for the infinite unit distance graph whose vertices are all the points in the plane, any graph automorphism must be an isometry.

If $\alpha$ is an algebraic number of modulus 1 that is not a root of unity, then the integer combinations of powers of $\alpha$ form a finitely generated subgroup of the additive group of complex numbers whose unit distance graph has infinite degree. 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

Main article: Hadwiger–Nelson problem

Unsolved problem in mathematics

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

More unsolved problems in mathematics

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, assuming 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, 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\geq 4$ labeled vertices is at most $${\binom {n(n-1)}{2n}}=O\left(2^{{\bigl (}4+o(1){\bigr )}n\log _{2}n}\right).$$ In contrast, the number of subgraphs of unit distance graphs is much larger, $$2^{{\bigl (}{\frac {1}{2}}+o(1){\bigr )}n^{2}}.$$

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 $n$ points have at most $n^{3/2}\beta (n)$ edges, where $\beta$ is a very slowly-growing function related to the inverse Ackermann function. This result may be used to give a similar bound on the number of edges of three-dimensional relative neighborhood graphs. In four or more dimensions, it is possible to represent any complete bipartite graph as a unit distance graph by placing the points on two perpendicular circles with a common center, so unit distance graphs can be dense graphs. The enumeration formulas for unit distance graphs generalize to higher dimensions, showing that in any dimension the number of strict unit distance graphs is much larger than the number of subgraphs of unit distance graphs.

Any graph may be embedded as a set of points in a sufficiently high dimension. The dimension needed to embed a graph so that all edges have unit distance, and the dimension needed to embed a graph so that the edges are exactly the unit distance pairs, may greatly differ from each other: the 2n-vertex crown graph may be embedded in four dimensions so that all its edges have unit length, but requires at least n − 2 dimensions to be embedded so that the edges are the only unit-distance pairs. The dimension needed to realize a graph as a strict unit graph (so that the edges are exactly the unit distance pairs) 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 Matoušek (1993) can be applied to this problem, yielding an algorithm for finding the edges of a unit distance graph in time $n^{4/3}2^{O(\log ^{*}n)}$ where $\log ^{*}$ is the slowly-growing iterated logarithm function.

It is NP-hard, and more specifically complete for the existential theory of the reals, to test whether a given graph is a subgraph of a unit distance graph, or is a strict unit distance graph. It is also NP-complete to determine whether a unit distance graph has a Hamiltonian cycle, even when the vertices of the graph all have integer coordinates.

References

Sources

• Ágoston, Péter; Pálvölgyi, Dömötör (April 2022), "An improved constant factor for the unit distance problem", Studia Scientiarum Mathematicarum Hungarica, 59 (1), Akademiai Kiado Zrt.: 40–57, arXiv:2006.06285, doi:10.1556/012.2022.01517
• Alon, Noga; Kupavskii, Andrey (2014), "Two notions of unit distance graphs" (PDF), Journal of Combinatorial Theory, Series A, 125: 1–17, doi:10.1016/j.jcta.2014.02.006, MR 3207464
• Beckman, F. S.; Quarles, D. A., Jr. (1953), "On isometries of Euclidean spaces", Proceedings of the American Mathematical Society, 4 (5): 810–815, doi:10.2307/2032415, JSTOR 2032415, MR 0058193{{citation}}: CS1 maint: multiple names: authors list (link)
• Braß, Peter (2002), "Combinatorial geometry problems in pattern recognition", Discrete & Computational Geometry, 28 (4): 495–510, doi:10.1007/s00454-002-2884-3, MR 1949897
• Carmi, Paz; Dujmović, Vida; Morin, Pat; Wood, David R. (2008), "Distinct distances in graph drawings", Electronic Journal of Combinatorics, 15 (1): Research Paper 107, arXiv:0804.3690, MR 2438579
• Chan, Timothy M.; Zheng, Da Wei (2022), "Hopcroft's problem, log-star shaving, 2d fractional cascading, and decision trees", in Naor, Joseph (Seffi); Buchbinder, Niv (eds.), Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 12, 2022, Society for Industrial and Applied Mathematics, pp. 190–210, arXiv:2111.03744, doi:10.1137/1.9781611977073.10
• Chilakamarri, Kiran B. (1995), "A 4-chromatic unit-distance graph with no triangles", Geombinatorics, 4 (3): 64–76, MR 1313386
• Chilakamarri, Kiran B.; Mahoney, Carolyn R. (1995), "Maximal and minimal forbidden unit-distance graphs in the plane", Bulletin of the Institute of Combinatorics and its Applications, 13: 35–43, MR 1314500, as cited by Globus & Parshall (2020)
• Clarkson, Kenneth L.; Edelsbrunner, Herbert; Guibas, Leonidas J.; Sharir, Micha; Welzl, Emo (1990), "Combinatorial complexity bounds for arrangements of curves and spheres", Discrete & Computational Geometry, 5 (2): 99–160, doi:10.1007/BF02187783, MR 1032370
• Erdős, Paul (1946), "On sets of distances of $n$ points", American Mathematical Monthly, 53 (5): 248–250, doi:10.2307/2305092, JSTOR 2305092
• Erdős, Paul; Harary, Frank; Tutte, William T. (1965), "On the dimension of a graph" (PDF), Mathematika, 12: 118–122, doi:10.1112/S0025579300005222, hdl:2027.42/152495, MR 0188096
• Erdős, Paul; Simonovits, Miklós (1980), "On the chromatic number of geometric graphs", Ars Combinatoria, 9: 229–246, as cited by Soifer (2008, p. 97)
• Gerbracht, Eberhard H.-A. (2009), Eleven unit distance embeddings of the Heawood graph, arXiv:0912.5395, Bibcode:2009arXiv0912.5395G
• Gervacio, Severino V.; Lim, Yvette F.; Maehara, Hiroshi (2008), "Planar unit-distance graphs having planar unit-distance complement", Discrete Mathematics, 308 (10): 1973–1984, doi:10.1016/j.disc.2007.04.050
• Globus, Aidan; Parshall, Hans (2020), "Small unit-distance graphs in the plane", Bulletin of the Institute of Combinatorics and its Applications, 90: 107–138, arXiv:1905.07829, MR 4156400
• Griffiths, Martin (June 2019), "103.27 A property of a particular unit-distance graph", The Mathematical Gazette, 103 (557): 353–356, doi:10.1017/mag.2019.74
• Horvat, Boris; Pisanski, Tomaž (2010), "Products of unit distance graphs", Discrete Mathematics, 310 (12): 1783–1792, doi:10.1016/j.disc.2009.11.035, MR 2610282
• Itai, Alon; Papadimitriou, Christos H.; Szwarcfiter, Jayme Luiz (1982), "Hamilton paths in grid graphs", SIAM Journal on Computing, 11 (4): 676–686, CiteSeerX 10.1.1.383.1078, doi:10.1137/0211056, MR 0677661
• Jaromczyk, Jerzy W.; Toussaint, Godfried T. (1992), "Relative neighborhood graphs and their relatives", Proceedings of the IEEE, 80 (9): 1502–1517, doi:10.1109/5.163414
• Kuperberg, Greg (1992), The Erdos kitty: At least $9050 in prizes!, Posting to usenet groups rec.puzzles and sci.math, archived from the original on 2006-09-29
• Langin, Katie (April 18, 2018), "Amateur mathematician cracks decades-old math problem", Science
• Lavollée, Jérémy; Swanepoel, Konrad J. (2022), "Bounding the number of edges of matchstick graphs", SIAM Journal on Discrete Mathematics, 36 (1): 777–785, arXiv:2108.07522, doi:10.1137/21M1441134, MR 4399020
• Maehara, Hiroshi (1991), "Distances in a rigid unit-distance graph in the plane", Discrete Applied Mathematics, 31 (2): 193–200, doi:10.1016/0166-218X(91)90070-D
• Maehara, Hiroshi (1992), "Extending a flexible unit-bar framework to a rigid one", Discrete Mathematics, 108 (1–3): 167–174, doi:10.1016/0012-365X(92)90671-2, MR 1189840
• Maehara, Hiroshi; Rödl, Vojtech (1990), "On the dimension to represent a graph by a unit distance graph", Graphs and Combinatorics, 6 (4): 365–367, doi:10.1007/BF01787703
• Matoušek, Jiří (1993), "Range searching with efficient hierarchical cuttings", Discrete & Computational Geometry, 10 (2): 157–182, doi:10.1007/BF02573972, MR 1220545
• O'Donnell, Paul (1995), "A 40 vertex 4-chromatic triangle-free unit distance graph", Geombinatorics, 5 (1): 31–34, MR 1337155
• Pach, János; Tardos, Gábor (2005), "Forbidden patterns and unit distances", in Mitchell, Joseph S. B.; Rote, Günter (eds.), Proceedings of the 21st ACM Symposium on Computational Geometry, Pisa, Italy, June 6-8, 2005, Association for Computing Machinery, pp. 1–9, doi:10.1145/1064092.1064096, MR 2460341
• Radchenko, Danylo (2021), "Unit distance graphs and algebraic integers", Discrete & Computational Geometry, 66 (1): 269–272, doi:10.1007/s00454-019-00152-4, MR 4270642
• Schaefer, Marcus (2013), "Realizability of graphs and linkages", in Pach, János (ed.), Thirty Essays on Geometric Graph Theory, Springer, pp. 461–482, CiteSeerX 10.1.1.220.9651, doi:10.1007/978-1-4614-0110-0_24, ISBN 978-1-4614-0109-4
• Soifer, Alexander (2008), The Mathematical Coloring Book, Springer-Verlag, ISBN 978-0-387-74640-1
• Spencer, Joel; Szemerédi, Endre; Trotter, William T. (1984), "Unit distances in the Euclidean plane", in Bollobás, Béla (ed.), Graph Theory and Combinatorics, London: Academic Press, pp. 293–308, ISBN 978-0-12-111760-3, MR 0777185
• Szemerédi, Endre (2016), "Erdős's unit distance problem", in Nash, John Forbes, Jr.; Rassias, Michael Th. (eds.), Open Problems in Mathematics, Cham, Switzerland: Springer, pp. 459–477, doi:10.1007/978-3-319-32162-2_15, MR 3526946{{citation}}: CS1 maint: multiple names: editors list (link)
• Tyszka, Apoloniusz (2000), "Discrete versions of the Beckman-Quarles theorem", Aequationes Mathematicae, 59 (1–2): 124–133, arXiv:math/9904047, doi:10.1007/PL00000119, MR 1741475
• Wormald, Nicholas (1979), "A 4-chromatic graph with a special plane drawing", Journal of the Australian Mathematical Society, Series A, 28 (1): 1–8, MR 0541161
• Žitnik, Arjana; Horvat, Boris; Pisanski, Tomaž (2012), "All generalized Petersen graphs are unit-distance graphs", Journal of the Korean Mathematical Society, 49 (3): 475–491, doi:10.4134/JKMS.2012.49.3.475, MR 2953031

External links

• Venkatasubramanian, Suresh, "Problem 39: Distances among Point Sets in R² and R³", The Open Problems Project
• Weisstein, Eric W., "Unit-Distance Graph", MathWorld