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

The smallest value of 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 (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 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 , 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. Mongolian tent graphs,

20. pan graphs,

21. path graphs ,

22. polyhexes,

23. polyiamonds,

24. polyominoes,

25. prism graphs (Horvat and Pisanski 2010),

26. Sierpiński carpet graphs,

27. Sierpiński gasket graphs,

28. stacked book graphs ,

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

30. star graphs ,

31. sunlet graphs ,

32. torus grid graphs ,

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

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