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
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
The main idea of Pisanski and his co-authors is that, in most cases, a generalized Petersen graph
Comments:
2010-01-04T20:11:29Z
Yes, the logic engine approach should definitely work.
Didn't Jack Edmonds prove that embedding with fixed edge length (no planarity required) is NP-hard? I can't find the citation, so I may be wrong, but I'm sure this is known. If you take that proof and replace longer edges with little gadgets, you should have the result. (Unless, of course, the edge lengths aren't polynomial. But I can't imagine that to be the case.)
2010-01-04T21:12:05Z
There was a result by Jeff Edmonds (not Jack) that it's NP-hard to tell whether a metric space can be embedded in a distance preserving way into a three-dimensional L∞ space, at SODA 2007 — is that the one you were thinking of?
2010-01-05T02:10:42Z
>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.
If the matchstick graph testing problem is NP-hard and it's a subproblem of the unit distance graph testing problem, then it is also NP-hard. right?
2010-01-05T03:59:20Z
Well, no. It could be true (though based on the logic engine argument it seems not to be true) that it's easy to test whether a graph is a unit distance graph but hard to figure out how to get the edges to be arranged in an uncrossed way.