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 all edge lengths are integers.[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]

Integral Fáry embedding of the octahedral graph K2,2,2

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 that consist either of removing a vertex of degree at most two or 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 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

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, posed by Stanislaw Ulam, 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]

See also

References

  1. ↑ 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.
  2. ↑ 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).
  3. 1 2 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 905393.
  4. 1 2 Sun, Timothy (2013), "Drawing some 4-regular planar graphs with integer edge lengths", Proc. Canadian Conference on Computational Geometry (CCCG 2013) (PDF).
  5. ↑ Brass, Peter; Moser, William O. J.; Pach, János (2005), Research Problems in Discrete Geometry, Springer, p. 250, ISBN 9780387299297, MR 2163782.
  6. ↑ Almering, J. H. J. (1963), "Rational quadrilaterals", Indagationes Mathematicae 25: 192–199, MR 0147447.
  7. ↑ Berry, T. G. (1992), "Points at rational distance from the vertices of a triangle", Acta Arithmetica 62 (4): 391–398, MR 1199630.
  8. ↑ Biedl, Therese (2011), "Drawing some planar graphs with integer edge-lengths", Proc. Canadian Conference on Computational Geometry (CCCG 2011) (PDF).
  9. ↑ Sun, Timothy (2011), "Rigidity-Theoretic Constructions of Integral Fary Embeddings", Proc. Canadian Conference on Computational Geometry (CCCG 2011) (PDF).
  10. ↑ 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 11, Cambridge University Press, pp. 132–135, ISBN 978-0-88385-315-3, MR 1133201.
  11. ↑ Kleber, Michael (2008), "Encounter at far point", Mathematical Intelligencer 1: 50–53, doi:10.1007/BF02985756.
  12. ↑ 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, MR 2419522.
  13. 1 2 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.
  14. ↑ 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.
This article is issued from Wikipedia - version of the Friday, April 17, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.