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  and path graph , respectively).

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  (Erdős 1946, Chvátal 1972) or  (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  (where  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.

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 subgraphs. (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 , 2, ... nodes as 0, 0, 0, 1, 1, 1, 3, 13, 55, ... (OEIS A308349). The corresponding numbers of simple connected unit-distance graphs on , 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.  bishop, black bishop, and white bishop graphs,

2. book graphs ,

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

4. camel graphs,

5. cube-connected cycle graphs,

6. cycle graphs ,

7. empty graphs  (trivially),

8. gear graphs,

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

10. giraffe graphs,

11. grid graphs  (Horvat and Pisanski 2010),

12. Hamming graphs  and ,

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

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

15. Jahangir graphs  with ,

16. ladder graphs ,

17. ladder rung graphs ,

18. Menger sponge graphs,

19. pan graphs,

20. path graphs ,

21. polyhexes,

22. polyiamonds,

23. polyominoes,

24. prism graphs  (Horvat and Pisanski 2010),

25. Sierpiński carpet graphs,

26. Sierpiński sieve graphs,

27. stacked book graphs ,

28. stacked prism graphs  (Horvat and Pisanski 2010),

29. star graphs ,

30. sunlet graphs ,

31. torus grid graphs ,

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

33. triangular honeycomb obtuse knight graphs,

34. web graphs, and

35. zebra graphs.

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

Families of unit-distance connected circulant graphs include:

1. cycle graphs ,

2. Cartesian products of prism graphs  and , yielding torus grid graphs .

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

graph
centipede graph
cycle graph
domino graph	6	7
Doyle graph	27	54
E graph	6	5
firecracker graph
gem graph	5	7
Golomb graph	10	18
grid graph
H graph	6	5
Hanoi graph
Harborth graph	52	104
Heawood graph	14	21
path graph
Moser spindle	7	11
pan graph
Sierpiński sieve graph
square graph	4	4
star graph
tadpole graph
theta-0 graph	7	8
triangle graph	3	3
wheel graph	7	12

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

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

Žitnik, A.; Horvat, B.; and Pisanski, T. "All Generalized Petersen Graphs are Unit-Distances Graphs." J. Korean Math. Soc. 49, 475-491, 2012.