 | ||
In mathematics, Harborth's conjecture states that every planar graph has a planar drawing in which all edge lengths are integers. This conjecture is named after Heiko Harborth, and (if true) would strengthen Fáry's theorem on the existence of straight-line drawings for every planar graph. For this reason, a drawing with integer edge lengths is also known as an integral Fáry embedding. Despite much subsequent research, Harborth's conjecture remains unsolved.
Contents
Special classes of graphs
Although Harborth's conjecture is not known to be true for all planar graphs, it has been proven for several special kinds of planar graph.
One class of graphs that have integral Fáry embeddings are the graphs that can be reduced to the empty graph by a sequence of operations of two types:
For such a graph, a rational Fáry embedding can be constructed incrementally by reversing this removal process, using the facts that the set of points that are at a rational distance from two given points are dense in the plane, and that if three points have rational distance between one pair and square-root-of-rational distance between the other two pairs, then the points at rational distances from all three are again dense in the plane. The distances in such an embedding can be made into integers by scaling the embedding by an appropriate factor. Based on this construction, the graphs known to have integral Fáry embeddings include the bipartite planar graphs, (2,1)-sparse planar graphs, planar graphs of treewidth at most 3, and graphs of degree at most four that either contain a diamond subgraph or are not 4-edge-connected.
In particular, the graphs that can be reduced to the empty graph by the removal only of vertices of degree at most two (the 2-degenerate planar graphs) include both the outerplanar graphs and the series-parallel graphs. However, for the outerplanar graphs a more direct construction of integral Fáry embeddings is possible, based on the existence of infinite subsets of the unit circle in which all distances are rational.
Additionally, integral Fáry embeddings are known for each of the five Platonic solids.
Related conjectures
A stronger version of Harborth's conjecture, posed by Kleber (2008), asks whether every planar graph has a planar drawing in which the vertex coordinates as well as the edge lengths are all integers. It is known to be true for 3-regular graphs, for graphs that have maximum degree 4 but are not 4-regular, and for planar 3-trees.
Another unsolved problem in geometry, the Erdős–Ulam problem, concerns the existence of dense subsets of the plane in which all distances are rational numbers. If such a subset existed, it would form a universal point set that could be used to draw all planar graphs with rational edge lengths (and therefore, after scaling them appropriately, with integer edge lengths). However, Ulam conjectured that dense rational-distance sets do not exist. According to the Erdős–Anning theorem, infinite non-collinear point sets with all distances being integers cannot exist. This does not rule out the existence of sets with all distances rational, but it does imply that in any such set the denominators of the rational distances must grow arbitrarily large.