Document Open Access Logo

An FPT Algorithm for the Embeddability of Graphs into Two-Dimensional Simplicial Complexes

Authors Éric Colin de Verdière, Thomas Magnard

PDF
Thumbnail PDF

File

LIPIcs.ESA.2021.32.pdf
  • Filesize: 0.73 MB
  • 17 pages

Document Identifiers

Author Details

Éric Colin de Verdière
  • LIGM, CNRS, Univ Gustave Eiffel, F-77454 Marne-la-Vallée, France
Thomas Magnard
  • LIGM, CNRS, Univ Gustave Eiffel, F-77454 Marne-la-Vallée, France

Funding

Partially supported by the ANR projects Min-Max (ANR-19-CE40-0014) and SoS (ANR-17-CE40-0033).

Acknowledgements

We would like to thank Arnaud de Mesmay for useful discussions.

Cite As Get BibTex

Éric Colin de Verdière and Thomas Magnard. An FPT Algorithm for the Embeddability of Graphs into Two-Dimensional Simplicial Complexes. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 32:1-32:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ESA.2021.32

Abstract

We consider the embeddability problem of a graph G into a two-dimensional simplicial complex C: Given G and C, decide whether G admits a topological embedding into C. The problem is NP-hard, even in the restricted case where C is homeomorphic to a surface.
It is known that the problem admits an algorithm with running time f(c)n^{O(c)}, where n is the size of the graph G and c is the size of the two-dimensional complex C. In other words, that algorithm is polynomial when C is fixed, but the degree of the polynomial depends on C. We prove that the problem is fixed-parameter tractable in the size of the two-dimensional complex, by providing a deterministic f(c)n³-time algorithm. We also provide a randomized algorithm with expected running time 2^{c^{O(1)}}n^{O(1)}.
Our approach is to reduce to the case where G has bounded branchwidth via an irrelevant vertex method, and to apply dynamic programming. We do not rely on any component of the existing linear-time algorithms for embedding graphs on a fixed surface; the only elaborated tool that we use is an algorithm to compute grid minors.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
  • Mathematics of computing → Graph algorithms
  • Mathematics of computing → Graphs and surfaces
  • Mathematics of computing → Topology
Keywords
  • computational topology
  • embedding
  • simplicial complex
  • graph
  • surface
  • fixed-parameter tractability

Metrics

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

Related Versions

References

  1. Isolde Adler, Martin Grohe, and Stephan Kreutzer. Computing excluded minors. In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 641-650, 2008. Google Scholar
  2. Christoph Buchheim, Markus Chimani, Carsten Gutwenger, Michael Jünger, and Petra Mutzel. Crossings and planarization. In Roberto Tamassia, editor, Handbook of graph drawing and visualization. Chapman and Hall, 2006. Google Scholar
  3. Chandra Chekuri and Julia Chuzhoy. Polynomial bounds for the grid-minor theorem. Journal of the ACM, 63(5):Article 40, 2016. Google Scholar
  4. É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. Google Scholar
  5. Éric Colin de Verdière and Arnaud de Mesmay. Testing graph isotopy on surfaces. Discrete & Computational Geometry, 51(1):171-206, 2014. Google Scholar
  6. Éric Colin de Verdière, Thomas Magnard, and Bojan Mohar. Embedding graphs into two-dimensional simplicial complexes. In Proceedings of the 34th International Symposium on Computational Geometry (SOCG), pages 27:1-27:14, 2018. Google Scholar
  7. Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized algorithms. Springer-Verlag, 2015. Google Scholar
  8. Tamal K. Dey and Sumanta Guha. Transforming curves on surfaces. Journal of Computer and System Sciences, 58:297-325, 1999. Google Scholar
  9. 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
  10. 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
  11. Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, Michał Pilipczuk, and Marcin Wrochna. Fully polynomial-time parameterized computations for graphs and matrices of low treewidth. ACM Transactions on Algorithms, 14(3):Article 34, 2018. Google Scholar
  12. John Hopcroft and Robert Tarjan. Efficient planarity testing. Journal of the ACM, 21(4):549-568, 1974. 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. Algorithmica, 81:3655-3691, 2019. 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. Seth M. Malitz. Genus g graphs have pagenumber O(√ g). Journal of Algorithms, 17:85-109, 1994. Google Scholar
  18. 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
  19. Bojan Mohar and Carsten Thomassen. Graphs on surfaces. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, 2001. Google Scholar
  20. 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
  21. Maurizio Patrignani. Planarity testing and embedding. In Roberto Tamassia, editor, Handbook of graph drawing and visualization. Chapman and Hall, 2006. Google Scholar
  22. 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
  23. Neil Robertson and Paul D. Seymour. Graph minors. XX. Wagner’s conjecture. Journal of Combinatorial Theory, Series B, 92:325-357, 2004. Google Scholar
  24. Marcus Schaefer. Toward a theory of planarity: Hanani-Tutte and planarity variants. Journal of Graph Algorithms and Applications, 17(4):367-440, 2013. Google Scholar
  25. John Stillwell. Classical topology and combinatorial group theory. Springer-Verlag, New York, second edition, 1993. Google Scholar
  26. 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