Misplaced Pages

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.

An unsolved problem of Paul Erdős asks how many edges a unit distance graph on ${\displaystyle n}$ vertices can have. The best known lower bound is slightly above linear in ${\displaystyle n}$—far from the upper bound, proportional to ${\displaystyle n^{4/3}}$. 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

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 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 or cactus graph may be realized as a unit distance graph.

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, and the Cartesian products of triangle graphs are the Hamming graphs ${\displaystyle H(d,3)}$.

Other specific graphs that are unit distance graphs include the Petersen graph, the Heawood graph, the wheel graph ${\displaystyle 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 non-strict unit distance graphs.

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

Paul Erdős (1946) posed the problem of estimating how many pairs of points in a set of ${\displaystyle 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. The hypercube graphs and Hamming graphs provide a lower bound on the number of unit distances, proportional to ${\displaystyle n\log n.}$ By considering points in a square grid with carefully chosen spacing, Erdős found an improved lower bound of the form $${\displaystyle n^{1+c/\log \log n}}$$ for a constant ${\displaystyle 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 $${\displaystyle {\sqrt{\frac {29n^{4}}{4}}}\approx 1.936n^{4/3}.}$$ 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.

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

Forbidden subgraphs

If a given graph ${\displaystyle G}$ is not a non-strict unit distance graph, neither is any supergraph ${\displaystyle H}$ of ${\displaystyle G}$. 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 ${\displaystyle G}$ is not a strict unit distance graph, then neither is any other ${\displaystyle H}$ that has ${\displaystyle 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 ${\displaystyle G}$ is a unit distance graph, of either type. ${\displaystyle G}$ is a non-strict unit distance graph, if and only if ${\displaystyle G}$ is not a supergraph of a forbidden graph for the non-strict unit distance graphs. ${\displaystyle G}$ is a strict unit distance graph, if and only if ${\displaystyle 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 ${\displaystyle K_{4}}$ and the complete bipartite graph ${\displaystyle K_{2,3}}$. For ${\displaystyle 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 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, one that cannot be formed by this gluing process.

The wheel graph ${\displaystyle 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 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 ${\displaystyle W_{7}}$, and the six-vertex graph formed from a triangular prism by removing an edge from one of its triangles.

Algebraic numbers and rigidity

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

If ${\displaystyle \alpha }$ is an algebraic number of modulus 1 that is not a root of unity, then the integer combinations of powers of ${\displaystyle \alpha }$ form a finitely generated subgroup of the additive group of complex numbers whose unit distance graph has infinite degree. For instance, ${\displaystyle \alpha }$ can be chosen as one of the two complex roots of the polynomial ${\displaystyle z^{4}-z^{3}-z^{2}-z+1}$, producing an infinite-degree unit distance graph with four generators.

Coloring

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, 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 ${\displaystyle n\geq 4}$ labeled vertices is at most $${\displaystyle {\binom {n(n-1)}{2n}}=O\left(2^{{\bigl (}4+o(1){\bigr )}n\log _{2}n}\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. In three dimensions, unit distance graphs of ${\displaystyle n}$ points have at most ${\displaystyle n^{3/2}\beta (n)}$ edges, where ${\displaystyle \beta }$ is a very slowly growing function related to the inverse Ackermann function. This result leads to a similar bound on the number of edges of three-dimensional relative neighborhood graphs. 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. 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 ${\displaystyle 2n}$-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 ${\displaystyle 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 Matoušek (1993) can be applied to this problem, yielding an algorithm for finding a planar point set's unit distance graph in time ${\displaystyle n^{4/3}2^{O(\log ^{*}n)}}$ where ${\displaystyle \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 (strict or non-strict) unit distance graph in the plane. 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.

References

Notes

1. Griffiths (2019).
2. ^ Alon & Kupavskii (2014).
3. ^ Gervacio, Lim & Maehara (2008).
4. ^ Carmi et al. (2008).
5. Huson & Sen (1995).
6. ^ Chilakamarri & Mahoney (1995).
7. ^ Erdős, Harary & Tutte (1965).
8. ^ Horvat & Pisanski (2010).
9. Brouwer & Haemers (2012).
10. Erdős, Harary & Tutte (1965); Griffiths (2019)
11. Gerbracht (2009).
12. Soifer (2008), pp. 14–15, 19.
13. Žitnik, Horvat & Pisanski (2012).
14. ^ Lavollée & Swanepoel (2022).
15. Szemerédi (2016).
16. Erdős (1990).
17. Spencer, Szemerédi & Trotter (1984); Clarkson et al. (1990); Pach & Tardos (2005); Ágoston & Pálvölgyi (2022)
18. Ágoston & Pálvölgyi (2022).
19. ^ Globus & Parshall (2020).
20. Soifer (2008), p. 94.
21. Maehara (1991, 1992).
22. Tyszka (2000).
23. Beckman & Quarles (1953).
24. Radchenko (2021).
25. Langin (2018); de Grey (2018)
26. Soifer (2008), p. 17.
27. Wormald (1979); Chilakamarri (1995); O'Donnell (1995).
28. Clarkson et al. (1990).
29. Jaromczyk & Toussaint (1992).
30. Erdős & Simonovits (1980).
31. Maehara & Rödl (1990).
32. ^ Braß (2002).
33. Matoušek (1993); see also Chan & Zheng (2022) for a closely related algorithm for listing point–line incidences in time ${\displaystyle O(n^{4/3})}$.
34. Schaefer (2013).
35. Itai, Papadimitriou & Szwarcfiter (1982).

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, S2CID 218479287
• 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, S2CID 12043969
• 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
• 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
• Brouwer, Andries E.; Haemers, Willem H. (2012), Spectra of Graphs, Universitext, New York: Springer, p. 178, doi:10.1007/978-1-4614-1939-6, ISBN 978-1-4614-1938-9, MR 2882891
• 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, doi:10.37236/831, MR 2438579, S2CID 2955082
• 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, S2CID 243847672
• 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, S2CID 28143698
• de Grey, Aubrey D. N. J. (2018), "The chromatic number of the plane is at least 5", Geombinatorics, 28: 5–18, arXiv:1804.02385, MR 3820926
• Erdős, Paul (1946), "On sets of distances of ${\displaystyle 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 (2): 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)
• Erdős, Paul (1990), "Some of my favourite unsolved problems", in Baker, A.; Bollobás, B.; Hajnal, A. (eds.), A tribute to Paul Erdős, Cambridge University Press, pp. 467–478, ISBN 0-521-38101-0, MR 1117038; see in particular p. 475
• 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, S2CID 233361952
• 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
• Huson, Mark L.; Sen, Arunabha (1995), "Broadcast scheduling algorithms for radio networks", Military Communications Conference, IEEE MILCOM '95, vol. 2, pp. 647–651, doi:10.1109/MILCOM.1995.483546, ISBN 0-7803-2489-7, S2CID 62039740
• 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
• 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, S2CID 237142624
• 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, S2CID 31148911
• 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, S2CID 18752227
• Radchenko, Danylo (2021), "Unit distance graphs and algebraic integers", Discrete & Computational Geometry, 66 (1): 269–272, doi:10.1007/s00454-019-00152-4, hdl:21.11116/0000-0006-9CFD-E, MR 4270642, S2CID 119682489
• 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
• 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, S2CID 14803182
• Wormald, Nicholas (1979), "A 4-chromatic graph with a special plane drawing", Journal of the Australian Mathematical Society, Series A, 28 (1): 1–8, doi:10.1017/S1446788700014865, MR 0541161, S2CID 124067465
• Ž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

• Geometric graphs