Unit distance graphs

The other day on the arXiv I saw an interesting paper on unit distance graphs by Gerbracht (to appear at STACS) that led me to some other recent discoveries on the subject.

A unit distance graph is what you get if you choose some set of points in the Euclidean plane as vertices and connect pairs of points by edges when the distance between them is exactly one. It's almost, but not quite, the same to ask for a labeling of the vertices of a graph by Euclidean points such that the endpoints of any edge have labels that are one unit apart: the two differences between these definitions are that a unit distance graph has to have each of its vertices at distinct locations, while the labeling doesn't, and that a unit distance graph can't have any non-adjacent pairs of vertices at unit distance from each other.

One of the major unanswered questions concerning unit distance graphs is how many colors are needed to color them, the so-called Hadwiger–Nelson problem. The answer is at least four and at most seven. The usual example of a unit distance graph requiring four colors is the seven-vertex Moser spindle, but there's another more symmetric graph that's only a little larger with the same property, the Golomb Graph, shown below. To see that this graph cannot be 3-colored, observe that there is only one way to 3-color the seven vertices of the triangulated hexagon, as shown, up to permutations of the colors. However this partial 3-coloring forces the three points of the hexagon that attach to the inner triangle to all be the same color. No matter how the inner triangle (shown in gray) is also 3-colored, one of its colors would coincide with the color of the neighboring attachment vertex. Thus, at least four colors are needed, and conversely it is not hard to find a 4-coloring of the graph.

Unfortunately, it's not at all easy to tell whether a given graph is a unit distance graph. In fact, I'm pretty sure that the Eades–Whitesides logic engine technique can be used to show that it's NP-hard to test whether a graph is a unit distance graph, but I haven't worked through the details carefully and I haven't succeeded in finding a paper that states the hardness of this problem explicitly. A very closely related problem is known to be NP-hard, though: it's also NP-hard to test whether a graph can be represented as a matchstick graph (unit distance graph without crossings): see Eades and Wormald and Cabello, Demaine, and Rote.

It's not even easy to answer the question of whether a graph is a unit distance graph for certain very specific small graphs. The Gerbracht paper answers this question for the Heawood graph, which describes the adjacencies between vertices and lines in the smallest possible finite projective plane. It solves a question that had been open since 1972, when Vašek Chvátal had suggested that the graphs formed from projective planes in this way were not unit distance graphs. The Heawood graph trivially has a labeling of the type described earlier (label the vertices representing points of the Fano plane by the Euclidean point \( (0,0) \) and label the vertices representing lines by the Euclidean point \( (1,0) \)) but it's not at all obvious that it has a unit distance representation, and despite the high degree of symmetry of the graph its unit distance representations are highly asymmetric.

Relatedly, Tomo Pisanski recently sent me a preprint of a paper by him with Žitnik and Horvat on unit distance graphs, "All generalized Petersen graphs are unit-distance graphs". A generalized Petersen graph is a graph that, like the Petersen graph or the Nauru graph \( G(12,5) \), can be formed by connecting each vertex of an outer polygon to the corresponding vertices of an inner star with the same number of points. The definition of a unit distance graph in this paper is a looser one in which vertices must be placed at distinct locations so that all edges have unit length, but some non-edges are also allowed to have unit length. As Erdős, Harary, and Tutte already observed, in some cases, this is easy: one can use a regular polygon for the outer polygon, a regular star with equal-length edges for the inner star, and twist the star by the correct angle to make the edges from outer to inner also have unit length. The same idea was also used by Golomb to form the layout of the Golomb graph shown above. However, this only works when the star is big enough and the outer polygon is small enough that corresponding vertices start out at less than unit distance and can have their distance increased by the twist; when the untwisted star is already at more than unit distance from the outer polygon, as happens in all but finitely many cases, this twisting idea is not enough.

The main idea of Pisanski and his co-authors is that, in most cases, a generalized Petersen graph \( G(n,k) \) can be permuted (by an automorphism of the cyclic group \( \mathbb{Z}_n \)) to take the form of an outer star connected to an inner star, and that by choosing the two stars carefully one can use the twist idea to form a unit distance representation. The only generalized Petersen graphs for which this twisted-double-star idea doesn't work are the prisms and the Nauru graph. For a prism, the outer and inner star are always congruent and twisting them to be unit distance apart causes their vertices to lie on top of each other, but one can instead translate two regular polygons with respect to each other. For the Nauru graph, the number \( 12 \) has too few non-divisors, so the nontrivial automorphisms of \( \mathbb{Z}_{12} \) don't give it a different form. Instead, they find a representation of the Nauru graph in which alternating vertices in the inner star and outer dodecagon are at different distances from the center of the drawing. The resulting drawing has the same amount of symmetry as the other generalized Petersen graphs (except for the prisms, which are less symmetric), but as a dihedral symmetry group rather than as in the twisted case a cyclic symmetry group. Here, redrawn from a figure in their paper, is one more to add to my collection of drawings of the Nauru graph:

---

Comments: