Document Open Access Logo

Shortest Path Embeddings of Graphs on Surfaces

Authors Alfredo Hubard, Vojtech Kaluža, Arnaud de Mesmay, Martin Tancer

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2016.43.pdf
  • Filesize: 0.57 MB
  • 16 pages

Document Identifiers

Author Details

Alfredo Hubard
Vojtech Kaluža
Arnaud de Mesmay
Martin Tancer

Cite As Get BibTex

Alfredo Hubard, Vojtech Kaluža, Arnaud de Mesmay, and Martin Tancer. Shortest Path Embeddings of Graphs on Surfaces. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 43:1-43:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.SoCG.2016.43

Abstract

The classical theorem of Fáry states that every planar graph can be represented by an embedding in which every edge is represented by a straight line segment. We consider generalizations of Fáry's theorem to surfaces equipped with Riemannian metrics. In this setting, we require that every edge is drawn as a shortest path between its two endpoints and we call an embedding with this property a shortest path embedding. The main question addressed in this paper is whether given a closed surface S, there exists a Riemannian metric for which every topologically embeddable graph admits a shortest path embedding. This question is also motivated by various problems regarding crossing numbers on surfaces.

We observe that the round metrics on the sphere and the projective plane have this property. We provide flat metrics on the torus and the Klein bottle which also have this property.

Then we show that for the unit square flat metric on the Klein bottle there exists a graph without shortest path embeddings. We show, moreover, that for large g, there exist graphs G embeddable into the orientable surface of genus g, such that with large probability a random hyperbolic metric does not admit a shortest path embedding of G, where the probability measure is proportional to the Weil-Petersson volume on moduli space.

Finally, we construct a hyperbolic metric on every orientable surface S of genus g, such that every graph embeddable into S can be embedded so that every edge is a concatenation of at most O(g) shortest paths.

Subject Classification

Keywords
  • Graph embedding
  • surface
  • shortest path
  • crossing number
  • hyperbolic geometry

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Dan Archdeacon and C. Paul Bonnington. Two maps on one surface. Journal of Graph Theory, 36(4):198-216, 2001. Google Scholar
  2. Robert Brooks and Eran Makover. Random construction of Riemann surfaces. J. Differential Geom., 68(1):121-157, 2004. Google Scholar
  3. Éric Colin de Verdière and Jeff Erickson. Tightening nonsimple paths and cycles on surfaces. SIAM Journal on Computing, 39(8):3784-3813, 2010. Google Scholar
  4. Éric Colin de Verdière, Alfredo Hubard, and Arnaud de Mesmay. Discrete systolic inequalities and decompositions of triangulated surfaces. Discrete & Computational Geometry, 53(3):587-620, 2015. Google Scholar
  5. Éric Colin de Verdière and Francis Lazarus. Optimal pants decompositions and shortest homotopic cycles on an orientable surface. Journal of the ACM, 54(4):Article 18, 2007. Google Scholar
  6. Yves Colin de Verdière. Comment rendre géodésique une triangulation d'une surface ? L'Enseignement Mathématique, 37:201-212, 1991. Google Scholar
  7. Manfredo P. do Carmo. Riemannian geometry. Birkhäuser, 1992. Google Scholar
  8. Cesim Erten and Stephen G. Kobourov. Simultaneous embedding of planar graphs with few bends. Journal of Graph Algorithms and Applications, 9(3):347-364, 2005. Google Scholar
  9. Benson Farb and Dan Margalit. A primer on mapping class groups. Princeton University Press, 2011. Google Scholar
  10. István Fáry. On straight line representations of planar graphs. Acta scientiarum mathematicarum (Szeged), 11:229-233, 1948. Google Scholar
  11. Michael Floater. One-to-one piecewise linear mappings over triangulations. Mathematics of Computation, 72(242):685-696, 2003. Google Scholar
  12. Jim Geelen, Tony Huynh, and R. Bruce Richter. Explicit bounds for graph minors. arXiv:1305.1451, 2013. Google Scholar
  13. Mikhael Gromov. Filling Riemannian manifolds. Journal of Differential Geometry, 1983. Google Scholar
  14. Larry Guth, Hugo Parlier, and Robert Young. Pants decompositions of random surfaces. Geometric and Functional Analysis, 21:1069-1090, 2011. Google Scholar
  15. Allen Hatcher. Algebraic topology. Cambridge University Press, 2002. Available at URL: http://www.math.cornell.edu/~hatcher/.
  16. Alfredo Hubard, Vojtěch Kaluža, Arnaud de Mesmay, and Martin Tancer. Shortest path embeddings of graphs on surfaces. arXiv preprint: http://arxiv.org/abs/1602.06778, 2016. Google Scholar
  17. Serge Lawrencenko. The irreducible triangulations of the torus. Ukrainskiĭ Geometricheskiĭ Sbornik, 30:52-62, 1987. Google Scholar
  18. Serge Lawrencenko and Seiya Negami. Irreducible triangulations of the Klein bottle. Journal of Combinatorial Theory, Series B, 70(2):265-291, 1997. Google Scholar
  19. Francis Lazarus, Michel Pocchiola, Gert Vegter, and Anne Verroust. Computing a canonical polygonal schema of an orientable triangulated surface. In Proceedings of the 17th Annual Symposium on Computational Geometry (SOCG), pages 80-89. ACM, 2001. Google Scholar
  20. Jiří Matoušek, Eric Sedgwick, Martin Tancer, and Uli Wagner. Untangling two systems of noncrossing curves. In Stephen Wismath and Alexander Wolff, editors, Graph Drawing, volume 8242 of Lecture Notes in Computer Science, pages 472-483. Springer International Publishing, 2013. Google Scholar
  21. Jiří Matoušek, Eric Sedgwick, Martin Tancer, and Uli Wagner. Embeddability in the 3-sphere is decidable. In Proceedings of the Thirtieth Annual Symposium on Computational Geometry, SOCG'14, pages 78-84. ACM, 2014. Google Scholar
  22. Maryam Mirzakhani. Growth of Weil-Petersson volumes and random hyperbolic surface of large genus. J. Differential Geom., 94(2):267-300, 06 2013. Google Scholar
  23. Bojan Mohar. Drawing graphs in the hyperbolic plane. In Graph Drawing, pages 127-136. Springer, 1999. Google Scholar
  24. Bojan Mohar and Carsten Thomassen. Graphs on surfaces. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, 2001. Google Scholar
  25. Seiya Negami. Crossing numbers of graph embedding pairs on closed surfaces. Journal of Graph Theory, 36(1):8-23, 2001. Google Scholar
  26. B. Osgood, R. Phillips, and P. Sarnak. Extremals of determinants of Laplacians. Journal of Functional Analysis, 80(1):148-211, 1988. Google Scholar
  27. R. Bruce Richter and Gelasio Salazar. Two maps with large representativity on one surface. Journal of Graph Theory, 50(3):234-245, 2005. Google Scholar
  28. Kenneth Stephenson. Introduction to circle packing: The theory of discrete analytic functions. Cambridge University Press, 2005. Google Scholar
  29. Thom Sulanke. Note on the irreducible triangulations of the Klein bottle. Journal of Combinatorial Theory, Series B, 96:964-972, 2006. Google Scholar
  30. Roberto Tamassia. On embedding a graph in the grid with the minimum number of bends. SIAM Journal on Computing, 16(3):421-444, 1987. Google Scholar
  31. Roberto Tamassia. Handbook of graph drawing and visualization. CRC press, 2013. Google Scholar
  32. William T. Tutte. How to draw a graph. Proceedings of the London Mathematical Society, 13:743-768, 1963. Google Scholar
  33. K. Wagner. Bemerkungen zum Vierfarbenproblem. Jahresbericht der Deutschen Mathematiker-Vereinigung, 46:26-32, 1936. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact