Document Open Access Logo

Embedding Graphs into Two-Dimensional Simplicial Complexes

Authors Éric Colin de Verdière, Thomas Magnard, Bojan Mohar

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2018.27.pdf
  • Filesize: 464 kB
  • 14 pages

Document Identifiers

Author Details

Éric Colin de Verdière
Thomas Magnard
Bojan Mohar

Cite As Get BibTex

Éric Colin de Verdière, Thomas Magnard, and Bojan Mohar. Embedding Graphs into Two-Dimensional Simplicial Complexes. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 27:1-27:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.SoCG.2018.27

Abstract

We consider the problem of deciding whether an input graph G admits a topological embedding into a two-dimensional simplicial complex C. This problem includes, among others, the embeddability problem of a graph on a surface and the topological crossing number of a graph, but is more general.
The problem is NP-complete when C is part of the input, and we give a polynomial-time algorithm if the complex C is fixed.
Our strategy is to reduce the problem to an embedding extension problem on a surface, which has the following form: Given a subgraph H' of a graph G', and an embedding of H' on a surface S, can that embedding be extended to an embedding of G' on S? Such problems can be solved, in turn, using a key component in Mohar's algorithm to decide the embeddability of a graph on a fixed surface (STOC 1996, SIAM J. Discr. Math. 1999).

Subject Classification

Keywords
  • computational topology
  • embedding
  • simplicial complex
  • graph
  • surface

Metrics

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

References

  1. Patrizio Angelini, Giuseppe Di Battista, Fabrizio Frati, Vít Jelínek, Jan Kratochvíl, Maurizio Patrignani, and Ignaz Rutter. Testing planarity of partially embedded graphs. ACM Transactions on Algorithms (TALG), 11(4):32, 2015. Google Scholar
  2. Dan Archdeacon. Topological graph theory. A survey. Congressus Numerantium, 115:5-54, 1996. Google Scholar
  3. William W. Boone. The word problem. Annals of Mathematics, 70:207-265, 1959. Google Scholar
  4. Martin Čadek, Marek Krčál, Jiří Matoušek, Lukáš Vokřínek, and Uli Wagner. Polynomial-time computation of homotopy groups and Postnikov systems in fixed dimension. SIAM Journal on Computing, 43(5):1728-1780, 2014. Google Scholar
  5. Éric Colin de Verdière. Computational topology of graphs on surfaces. In Jacob E. Goodman, Joseph O'Rourke, and Csaba Toth, editors, Handbook of Discrete and Computational Geometry, chapter 23. CRC Press LLC, third edition, 2018. See URL: http://www.arxiv.org/abs/1702.05358.
  6. Éric Colin de Verdière and Arnaud de Mesmay. Testing graph isotopy on surfaces. Discrete &Computational Geometry, 51(1):171-206, 2014. Google Scholar
  7. Erik Demaine, Shay Mozes, Christian Sommer, and Siamak Tazari. Algorithms for planar graphs and beyond, 2011. Course notes available at URL: http://courses.csail.mit.edu/6.889/fall11/lectures/.
  8. Tamal K. Dey, Herbert Edelsbrunner, and Sumanta Guha. Computational topology. In Bernard Chazelle, Jacob E. Goodman, and Richard Pollack, editors, Advances in Discrete and Computational Geometry - Proc. 1996 AMS-IMS-SIAM Joint Summer Research Conf. Discrete and Computational Geometry: Ten Years Later, number 223 in Contemporary Mathematics, pages 109-143. AMS, 1999. Google Scholar
  9. Tamal K. Dey and Sumanta Guha. Transforming curves on surfaces. Journal of Computer and System Sciences, 58:297-325, 1999. Google Scholar
  10. David Eppstein. Dynamic generators of topologically embedded graphs. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 599-608, 2003. Google Scholar
  11. Jeff Erickson. Combinatorial optimization of cycles and bases. In Afra Zomorodian, editor, Computational topology, Proceedings of Symposia in Applied Mathematics. AMS, 2012. Google Scholar
  12. Jeff Erickson and Kim Whittlesey. Transforming curves on surfaces redux. In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1646-1655, 2013. Google Scholar
  13. Ken-ichi Kawarabayashi, Bojan Mohar, and Bruce Reed. A simpler linear time algorithm for embedding graphs into an arbitrary surface and the genus of graphs of bounded tree-width. In Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 771-780, 2008. Google Scholar
  14. Ken-ichi Kawarabayashi and Bruce Reed. Computing crossing number in linear time. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC), pages 382-390, 2007. Google Scholar
  15. Tomasz Kociumaka and Marcin Pilipczuk. Deleting vertices to graphs of bounded genus. arXiv:1706.04065, 2017. Google Scholar
  16. Francis Lazarus and Julien Rivaud. On the homotopy test on surfaces. In Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 440-449, 2012. Google Scholar
  17. Sóstenes Lins. Graph-encoded maps. Journal of Combinatorial Theory, Series B, 32:171-181, 1982. Google Scholar
  18. Seth M. Malitz. Genus g graphs have pagenumber O(√ g). Journal of Algorithms, 17:85-109, 1994. Google Scholar
  19. Jiří Matoušek, Eric Sedgwick, Martin Tancer, and Uli Wagner. Embeddability in the 3-sphere is decidable. Journal of the ACM, 2018. To appear. Preliminary version in Symposium on Computational Geometry 2014. Google Scholar
  20. Jiří Matoušek, Martin Tancer, and Uli Wagner. Hardness of embedding simplicial complexes in R^d. Journal of the European Mathematical Society, 13(2):259-295, 2011. Google Scholar
  21. Bojan Mohar. On the minimal genus of 2-complexes. Journal of Graph Theory, 24(3):281-290, 1997. Google Scholar
  22. Bojan Mohar. A linear time algorithm for embedding graphs in an arbitrary surface. SIAM Journal on Discrete Mathematics, 12(1):6-26, 1999. Google Scholar
  23. Bojan Mohar and Carsten Thomassen. Graphs on surfaces. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, 2001. Google Scholar
  24. Colm Ó Dúnlaing, Colum Watt, and David Wilkins. Homeomorphism of 2-complexes is equivalent to graph isomorphism. International Journal of Computational Geometry &Applications, 10:453-476, 2000. Google Scholar
  25. Maurizio Patrignani. Planarity testing and embedding. In Roberto Tamassia, editor, Handbook of graph drawing and visualization. Chapman and Hall, 2006. Google Scholar
  26. Neil Robertson and Paul D. Seymour. Graph minors. XIII. The disjoint paths problem. Journal of Combinatorial Theory, Series B, 63(1):65-110, 1995. Google Scholar
  27. John Stillwell. Classical topology and combinatorial group theory. Springer-Verlag, New York, second edition, 1993. Google Scholar
  28. Carsten Thomassen. The graph genus problem is NP-complete. Journal of Algorithms, 10(4):568-576, 1989. 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