Harborth's conjecture
 |
Unsolved problem in mathematics: Does every planar graph have an integral Fáry embedding? (more unsolved problems in mathematics)
|
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]Cite error: Closing </ref> missing for <ref> tag[3] 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][5][6]
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.[7]
Additionally, integral Fáry embeddings are known for each of the five Platonic solids.[8]
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.[9] It is known to be true for 3-regular graphs,[10] for graphs that have maximum degree 4 but are not 4-regular,[11] and for planar 3-trees.[11]
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.[12] 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
- 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
- ↑ Hartsfield, Nora; Ringel, Gerhard (2013), Pearls in Graph Theory: A Comprehensive Introduction, Dover Books on Mathematics, Courier Dover Publications, p. 247, ISBN 9780486315522. 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. Kemnitz and Harborth credit the original publication of this conjecture to (Harborth Kemnitz).
- ↑ 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, https://eudml.org/doc/206501.
- ↑ Cite error: Invalid
<ref>tag; no text was provided for refs namedSun13 - ↑ Biedl, Therese (2011), "Drawing some planar graphs with integer edge-lengths", Proc. Canadian Conference on Computational Geometry (CCCG 2011), http://www.cccg.ca/proceedings/2011/papers/paper36.pdf.
- ↑ Sun, Timothy (2011), "Rigidity-Theoretic Constructions of Integral Fary Embeddings", Proc. Canadian Conference on Computational Geometry (CCCG 2011), http://www.cccg.ca/proceedings/2011/papers/paper20.pdf.
- ↑ "Problem 10: Does the plane contain a dense rational set?", Old and New Unsolved Problems in Plane Geometry and Number Theory, Dolciani mathematical expositions, 11, Cambridge University Press, 1991, pp. 132–135, ISBN 978-0-88385-315-3, https://books.google.com/books?id=tRdoIhHh3moC&pg=PA132.
- ↑ Cite error: Invalid
<ref>tag; no text was provided for refs namedhkms - ↑ Kleber, Michael (2008), "Encounter at far point", Mathematical Intelligencer 1: 50–53, doi:10.1007/BF02985756.
- ↑ 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, doi:10.1002/jgt.20304.
- ↑ 11.0 11.1 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.
- ↑ Solymosi, Jozsef; de Zeeuw, Frank (2010), "On a question of Erdős and Ulam", Discrete and Computational Geometry 43 (2): 393–401, doi:10.1007/s00454-009-9179-x.
 |  |
