TOPICS
Search

Unit-Distance Graph


A unit-distance graph is a distance graph having an embedding in the Euclidean plane (unit-distance embedding) in which vertices are distinct points and all edges are of length 1. It is therefore a special case of an integral embedding. By their definition, unit-distance graphs have graph dimension of 2 or less (with 0 and 1 corresponding to the trivial connected cases of the singleton graph K_1 and path graph P_n, respectively).

The smallest value of d for which a graph is unit distance is called its graph dimension.

A disconnected graph is unit-distance iff each of its connected components is unit-distance. Similarly, a connected graph is unit-distance if and only if each of its blocks is unit-distance (Chilakamarri and Mahoney 1995, Globus and Parshall 2019). This is because biconnected components are joined in the original graph either at a single single point at which them may be split or by graph bridges. Since bridges can always be drawn with unit length, if the components are all unit-distance, then so is the graph obtained by connecting them either directly or with bridges.

Determining if a graph is unit-distance is NP-hard (Schaefer 2013, pp. 461-482; Globus and Parshall 2019).

Any graph that contains complete bipartite K_(2,3) (Erdős 1946, Chvátal 1972) or K_4 (Chvátal 1972) subgraph as a vertex-induced subgraph is not a unit-distance graph (Horvat and Pisanski 2010). To see the former, draw unit circles around two points and note that the circles cannot intersect in three places. (However, the diamond graph K_4-e (where e is any edge) is unit-distance.) In addition, any graph with chromatic number greater than 7 is not a unit-distance graph (Horvat and Pisanski 2010).

The graph Cartesian product of two unit-distance graphs is also a unit-distance graph (Erdős et al. 1965, Buckley and Harary 1988, Horvat and Pisanski 2010). This immediately establishes the unit-distance status of a number of families of graphs.

UnitDistanceForbidden7

Call a graph that is not unit-distance "forbidden," and call a forbidden graph minimal if each of its proper subgraphs is unit-distance. Purdy and Purdy (1988) attempted to classify the minimal forbidden graphs on 7 vertices, but their results contained errors. Chilakamarri and Mahoney (1995) subsequently proved that a graph on 7 or fewer vertices is unit-distance iff it contains one of the above seven minimal graphs as a forbidden subgraph. (This result was also obtained independently by H. Parshall and E. Weisstein in April 2018, though Weisstein's set included graphs reducible to minimal ones by edge deletions.) Globus and Parshall (2019) found there to be 13 minimal forbidden 8-node graphs and 55 minimal forbidden 9-node graphs. This gives the numbers of minimal unit-distance forbidden graphs on n=1, 2, ... nodes as 0, 0, 0, 1, 1, 1, 3, 13, 55, ... (OEIS A308349). The corresponding numbers of simple connected unit-distance graphs on n=1, 2, ... nodes are 1, 1, 2, 5, 13, 51, 222, 1313, 9639, ... (OEIS A059103).

Unit-distance graphs are closely related to the Hadwiger-Nelson problem, which asks the chromatic number of the plane (i.e., the minimum number of colors needed to color the plane if no two points at unit distance one from one another are given the same color). The value is currently known to be 5, 6, or 7, but discovery of a unit-distance graph with chromatic number equal to one of these values would provide tighter bounds on these results.

A unit-distance graph that is rigid and contains a regular polygon as subgraph is known as a braced polygon.

Classes of graphs that are unit-distance include the following:

1. 3×n bishop, black bishop, and white bishop graphs,

2. book graphs S_(n+1) square P_2,

3. cactus graphs (Erdős et al. 1965),

4. camel graphs,

5. cube-connected cycle graphs,

6. cycle graphs C_n,

7. empty graphs K^__n (trivially),

8. gear graphs,

9. generalized Petersen graph (Žitnik et al. 2012),

10. giraffe graphs,

11. grid graphs P_m square P_n (Horvat and Pisanski 2010),

12. Hamming graphs H(d,2) and H(d,3),

13. hypercube graphs Q_n (Erdős et al. 1965),

14. I graphs (Žitnik et al. 2012),

15. Jahangir graphs J_(n,m) with n>1,

16. ladder graphs P_m square P_2,

17. ladder rung graphs nP_2,

18. Menger sponge graphs,

19. Mongolian tent graphs,

20. pan graphs,

21. path graphs P_n,

22. polyhexes,

23. polyiamonds,

24. polyominoes,

25. prism graphs C_m square P_2 (Horvat and Pisanski 2010),

26. Sierpiński carpet graphs,

27. Sierpiński gasket graphs,

28. stacked book graphs S_(m+1) square P_n,

29. stacked prism graphs C_m square P_n (Horvat and Pisanski 2010),

30. star graphs S_n,

31. sunlet graphs C_n circledot K_1,

32. torus grid graphs C_4 square C_n,

33. trees (Erdős et al. 1965), and

34. triangular honeycomb acute knight graphs,

35. triangular honeycomb obtuse knight graphs,

36. web graphs, and

37. zebra graphs.

The only unit-distance wheel graph is W_7 (Buckley and Harary 1988).

Families of unit-distance connected circulant graphs include:

1. cycle graphs C_n=Ci_n(1),

2. Cartesian products of prism graphs C_n square P_2 and P_2, yielding torus grid graphs C_n square P_2 square P_2=C_4 square C_n=Ci_(n(n+1))(n,n+1).

UnitDistanceGraphs

A number of unit-distance graphs are illustrated above.

The following table summarizes some named unit-distance graphs (or, more generally, graphs all of whose edges are the same length).

UnitDistanceCubicSymmetric

Many cubic symmetric graphs (excepting the tetrahedral graph, utility graph, and possibly others) have unit-distance embeddings, as illustrated above in embeddings mainly due to Gerbracht (2008, pers. comm., Dec. 2009-Jan. 2010).


See also

Braced Polygon, de Grey Graphs, Distance Graph, Golomb Graph, Graph Dimension, Graph Embedding, Hadwiger-Nelson Problem, Heule Graphs, Integral Embedding, Matchstick Graph, Mixon Graphs, Moser Spindle, Parts Graphs, Tadpole Graph, Unit-Distance Embedding, Unit Neighborhood Graph, Voronov-Neopryatnaya-Dergachev Graphs, Wormald Graph

Explore with Wolfram|Alpha

References

Anning, N. H. and Erdős, P. "Integral Distances." Bull. Amer. Math. Soc. 51, 598-600, 1945.Buckley, F. and Harary, F. "On the Euclidean Dimension of a Wheel." Graphs and Combin. 4, 23-30, 1988.Chilakamarri, K. B. "Unit Distance Graphs in Rational n-Space." Discr. Math. 69, 213-218, 1988.Chilakamarri, K. B. and Mahoney, C. R. "Maximal and Minimal Forbidden Unit-Distance Graphs in the Plane." Bull. Inst. Combin. Appl. 13, 35-43, 1995.Chvátal, V. Problem 21 in Chvátal, V.; Klarner, D. E.; and Knuth, D. E. "Selected Combinatorial Research Problems." Tech. Report STAN-CS-72-292, Computer Science Department, School of Humanities and Sciences. Stanford, CA: Stanford University, pp. 11-13, 1972.Eades, P. and Wormald, N. C. "Fixed Edge-Length Graph Drawing Is NP-Hard." Discr. Appl. Math. 28, 111-134, 1990.Eppstein, D. "Unit Distance Graphs." Jan. 4, 2010. http://11011110.livejournal.com/188807.html.Erdős, P. "On Sets of Distances of n Points." Amer. Math. Monthly 53, 248-250, 1946.Erdős, P.; Harary, F.; and Tutte, W. T. "On the Dimension of a Graph." Mathematika 12, 118-122, 1965.Gerbracht, E. H.-A. "On the Unit Distance Embeddability of Connected Cubic Symmetric Graphs." Kolloquium über Kombinatorik. Magdeburg, Germany. Nov. 15, 2008.Globus, A. and Parshall, H. "Small Unit-Distance Graphs in the Plane." Bull. Inst. Combin. Appl. 90, 107-138, 2020.Hochberg, R. "A Program for Proving That a Given Graph Is Not a Unit-Distance Graph: Preliminary Report." In Proceedings of the 44th Annual Southeast Regional Conference (Melbourne, Florida, March 10-12, 2006). ACM-SE 44. 2006.Hochberg, R. and O'Donnell, P. "Some 4-Chromatic Unit-Distance Graphs Without Small Cycles." Geombinatorics 5, 137-141, 1996.Horvat, B. and Pisanski, T. "Products of Unit Distance Graphs." Disc. Math. 310, 1783-1792, 2010.Kurz, S. "Fast Recognition of Planar Non Unit Distance Graphs - Searching the Minimum 4-Regular Planar Unit Distance Graph." Submitted. http://www.wm.uni-bayreuth.de/fileadmin/Sascha/Publikationen/unmasking_non_unit_distance_graphs.pdf.Maehara, H. "On Euclidean Dimension of a Complete Multipartite Graph." Discr. Math. 72, 285-289, 1988.Maehara, H. "Note on Induced Subgraphs of the Unit Distance Graph." Discr. Comput. Geom. 4, 15-18, 1989.Maehara, H. "Distances in a Rigid Unit-Distance Graph in the Plane." Discr. Appl. Math. 31, 193-200, 1991.Maehara, H. "Distance Graphs in Euclidean Space." Ryukyu Math. J. 5, 33-51, 1992.Maehara, H. and Rödl, V. "On the Dimension to Represent a Graph by a Unit Distance Graph." Graphs Combin. 6, 365-367, 1990.Moser, L. and Moser, W. "Problem 10." Canad. Math. Bull. 4, 187-189, 1961.Purdy, C. and Purdy, G. "Minimal Forbidden Distance One Graphs." Congr. Numer. 66, 165-172, 1988.Schaefer, M. "Realizability of Graphs and Linkages." In Thirty Essays on Geometric Graph Theory. New York: Springer, pp. 461-482, 2013.Sloane, N. J. A. Sequences A059103 and A308349 in "The On-Line Encyclopedia of Integer Sequences."Soifer, A. The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of Its Creators. New York: Springer, 2008.Soifer, A. The New Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of Its Creators, 2nd ed. New York: Springer, 2024.Žitnik, A.; Horvat, B.; and Pisanski, T. "All Generalized Petersen Graphs are Unit-Distances Graphs." J. Korean Math. Soc. 49, 475-491, 2012.

Referenced on Wolfram|Alpha

Unit-Distance Graph

Cite this as:

Weisstein, Eric W. "Unit-Distance Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Unit-DistanceGraph.html

Subject classifications