Harborth's conjecture
In mathematics, Harborth's conjecture states that every planar graph has a planar drawing in which every edge is a straight segment of integer length.[1][2][3] 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.[4] Despite much subsequent research, Harborth's conjecture remains unsolved.[5]
Special classes of graphs
[edit]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:
- Removing a vertex of degree at most two.
- Replacing a vertex of degree three by an edge between two of its neighbors. (If such an edge already exists, the degree three vertex can be removed without adding another edge between its neighbors.)
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.[6][7] 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.[4][8][9]
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.[10]
Additionally, integral Fáry embeddings are known for each of the five Platonic solids.[3]
Related conjectures
[edit]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.[11] It is known to be true for 3-regular graphs,[12] for graphs that have maximum degree 4 but are not 4-regular,[13] and for planar 3-trees.[13]
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.[14] 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.
See also
[edit]- Integer triangle, an integral Fáry embedding of the triangle graph
- Matchstick graph, a graph that can be drawn planarly with all edge lengths equal to 1
- Erdős–Diophantine graph, a complete graph with integer distances that cannot be extended to a larger complete graph with the same property
- Euler brick, an integer-distance realization problem in three dimensions
References
[edit]- ^ Hartsfield, Nora; Ringel, Gerhard (2013), Pearls in Graph Theory: A Comprehensive Introduction, Dover Books on Mathematics, Courier Dover Publications, p. 247, ISBN 9780486315522, MR 2047103. Reprint of 1994 Academic Press edition; the same name is given to the conjecture in the original 1990 edition.
- ^ Kemnitz, Arnfried; Harborth, Heiko (2001), "Plane integral drawings of planar graphs", Discrete Mathematics, Graph theory (Kazimierz Dolny, 1997), 236 (1–3): 191–195, doi:10.1016/S0012-365X(00)00442-8, MR 1830610. Kemnitz and Harborth credit the original publication of this conjecture to Harborth et al. (1987).
- ^ a b Harborth, Heiko; Kemnitz, Arnfried; Möller, Meinhard; Süssenbach, Andreas (1987), "Ganzzahlige planare Darstellungen der platonischen Körper", Elemente der Mathematik, 42 (5): 118–122, MR 0905393.
- ^ a b Sun, Timothy (2013), "Drawing some 4-regular planar graphs with integer edge lengths", Proc. Canadian Conference on Computational Geometry (CCCG 2013) (PDF).
- ^ Brass, Peter; Moser, William O. J.; Pach, János (2005), Research Problems in Discrete Geometry, Springer, p. 250, ISBN 9780387299297, MR 2163782.
- ^ Almering, J. H. J. (1963), "Rational quadrilaterals", Indagationes Mathematicae, 25: 192–199, doi:10.1016/S1385-7258(63)50020-1, MR 0147447.
- ^ Berry, T. G. (1992), "Points at rational distance from the vertices of a triangle", Acta Arithmetica, 62 (4): 391–398, doi:10.4064/aa-62-4-391-398, MR 1199630.
- ^ Biedl, Therese (2011), "Drawing some planar graphs with integer edge-lengths", Proc. Canadian Conference on Computational Geometry (CCCG 2011) (PDF).
- ^ Sun, Timothy (2011), "Rigidity-Theoretic Constructions of Integral Fary Embeddings", Proc. Canadian Conference on Computational Geometry (CCCG 2011) (PDF).
- ^ Klee, Victor; Wagon, Stan (1991), "Problem 10: Does the plane contain a dense rational set?", Old and New Unsolved Problems in Plane Geometry and Number Theory, Dolciani mathematical expositions, vol. 11, Cambridge University Press, pp. 132–135, ISBN 978-0-88385-315-3, MR 1133201.
- ^ Kleber, Michael (2008), "Encounter at far point", Mathematical Intelligencer, 1: 50–53, doi:10.1007/BF02985756, S2CID 120522596.
- ^ Geelen, Jim; Guo, Anjie; McKinnon, David (2008), "Straight line embeddings of cubic planar graphs with integer edge lengths", Journal of Graph Theory, 58 (3): 270–274, CiteSeerX 10.1.1.64.4523, doi:10.1002/jgt.20304, MR 2419522, S2CID 1856482.
- ^ a b Benediktovich, Vladimir I. (2013), "On rational approximation of a geometric graph", Discrete Mathematics, 313 (20): 2061–2064, doi:10.1016/j.disc.2013.06.018, MR 3084247.
- ^ Solymosi, Jozsef; de Zeeuw, Frank (2010), "On a question of Erdős and Ulam", Discrete and Computational Geometry, 43 (2): 393–401, arXiv:0806.3095, doi:10.1007/s00454-009-9179-x, MR 2579704, S2CID 15288690.