Document Open Access Logo

Triconnected Planar Graphs of Maximum Degree Five are Subhamiltonian

Authors Michael Hoffmann , Boris Klemz

PDF
Thumbnail PDF

File

LIPIcs.ESA.2019.58.pdf
  • Filesize: 0.64 MB
  • 14 pages

Document Identifiers

Author Details

Michael Hoffmann
  • Department of Computer Science, ETH Zürich, Zürich, Switzerland
Boris Klemz
  • Institute of Computer Science, Freie Universität Berlin, Berlin, Germany

Funding

  • Hoffmann, Michael: Research supported by the Swiss National Science Foundation within the collaborative DACH project Arrangements and Drawings as SNSF Project 200021E-171681.

Acknowledgements

This research was initiated during the Geometric Graphs Week 2016 at UPC, Barcelona, and reinvigorated at the Lorentz Center Workshop on Fixed-Parameter Computational Geometry 2018 in Leiden. We thank the organizers and participants for the stimulating atmosphere and, in particular, Oswin Aichholzer, Bahareh Banyassady, Philipp Kindermann, Irina Kostitsyna, and Fabian Lipp for initial discussions about the problem.

Cite As Get BibTex

Michael Hoffmann and Boris Klemz. Triconnected Planar Graphs of Maximum Degree Five are Subhamiltonian. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 58:1-58:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ESA.2019.58

Abstract

We show that every triconnected planar graph of maximum degree five is subhamiltonian planar. A graph is subhamiltonian planar if it is a subgraph of a Hamiltonian planar graph or, equivalently, if it admits a 2-page book embedding. In fact, our result is stronger because we only require vertices of a separating triangle to have degree at most five, all other vertices may have arbitrary degree. This degree bound is tight: We describe a family of triconnected planar graphs that are not subhamiltonian planar and where every vertex of a separating triangle has degree at most six. Our results improve earlier work by Heath and by Bauernöppel and, independently, Bekos, Gronemann, and Raftopoulou, who showed that planar graphs of maximum degree three and four, respectively, are subhamiltonian planar. The proof is constructive and yields a quadratic time algorithm to obtain a subhamiltonian plane cycle for a given graph.
As one of our main tools, which might be of independent interest, we devise an algorithm that, in a given 3-connected plane graph satisfying the above degree bounds, collapses each maximal separating triangle into a single edge such that the resulting graph is biconnected, contains no separating triangle, and no separation pair whose vertices are adjacent.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Paths and connectivity problems
  • Mathematics of computing → Graphs and surfaces
  • Theory of computation → Computational geometry
  • Human-centered computing → Graph drawings
Keywords
  • Graph drawing
  • book embedding
  • Hamiltonian graph
  • planar graph
  • bounded degree graph
  • graph augmentation
  • computational geometry
  • SPQR decomposition

Metrics

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

References

  1. Armen S. Asratian and Nikolay K. Khachatrian. Some localization theorems on Hamiltonian circuits. J. Combin. Theory Ser. B, 49(2):287-294, 1990. URL: https://doi.org/10.1016/0095-8956(90)90032-U.
  2. Frank Bauernöppel. Degree Bounds and Subhamiltonian Cycles in Planar Graphs. J. Inf. Process. Cybern., 23(10-11):529-536, 1987. Google Scholar
  3. Michael A. Bekos, Martin Gronemann, and Chrysanthi N. Raftopoulou. Two-page book embeddings of 4-planar graphs. Algorithmica, 75(1):158-185, 2016. URL: https://doi.org/10.1007/s00453-015-0016-8.
  4. Frank Bernhart and Paul C. Kainen. The book thickness of a graph. J. Combin. Theory Ser. B, 27(3):320-331, 1979. URL: https://doi.org/10.1016/0095-8956(79)90021-2.
  5. Therese C. Biedl, Goos Kant, and Michael Kaufmann. On triangulating planar graphs under the four-connectivity constraint. Algorithmica, 19(4):427-446, 1997. URL: https://doi.org/10.1007/PL00009182.
  6. Jean Cardinal, Michael Hoffmann, Vincent Kusters, Csaba D. Tóth, and Manuel Wettstein. Arc diagrams, flip distances, and Hamiltonian triangulations. Comput. Geom. Theory Appl., 68:206-225, 2018. URL: https://doi.org/10.1016/j.comgeo.2017.06.001.
  7. Norishige Chiba and Takao Nishizeki. The Hamiltonian cycle problem is linear-time solvable for 4-connected planar graphs. J. Algorithms, 10(2):187-211, 1989. URL: https://doi.org/10.1016/0196-6774(89)90012-6.
  8. Mark de Berg, Otfried Cheong, Marc J. van Kreveld, and Mark H. Overmars. Computational geometry: algorithms and applications, 3rd Edition. Springer, 2008. URL: https://doi.org/10.1007/978-3-540-77974-2.
  9. Gabriel A. Dirac. Some theorems on abstract graphs. Proc. London Math. Soc., s3-2(1):69-81, 1952. URL: https://doi.org/10.1112/plms/s3-2.1.69.
  10. Günter Ewald. Hamiltonian Circuits in Simplicial Complexes. Geom. Dedicata, 2:115-125, 1973. URL: https://doi.org/10.1007/BF00149287.
  11. Michael R. Garey, David S. Johnson, and Robert E. Tarjan. The planar Hamiltonian circuit problem is NP-complete. SIAM J. Comput., 5(4):704-714, 1976. URL: https://doi.org/10.1137/0205049.
  12. Xiaxia Guan and Weihua Yang. Embedding 5-planar graphs in three pages. CoRR, abs/1801.07097, 2018. URL: http://arxiv.org/abs/1801.07097.
  13. Carsten Gutwenger and Petra Mutzel. A linear time implementation of SPQR-trees. In Proc. 8th Internat. Sympos. Graph Drawing (GD'00), volume 1984 of LNCS, pages 77-90. Springer, 2000. URL: https://doi.org/10.1007/3-540-44541-2_8.
  14. Lenwood S. Heath. Algorithms for embedding graphs in books. Phd thesis, University of North Carolina, Chapel Hill, 1985. URL: http://www.cs.unc.edu/techreports/85-028.pdf.
  15. Jacob Holm, Giuseppe F. Italiano, Adam Karczmarz, Jakub Łącki, and Eva Rotenberg. Decremental SPQR-trees for planar graphs. In Proc. 26th Annu. European Sympos. Algorithms (ESA 2018), volume 112 of LIPIcs, pages 46:1-46:16, 2018. URL: https://doi.org/10.4230/LIPIcs.ESA.2018.46.
  16. Øystein Ore. Note on Hamilton circuits. Amer. Math. Monthly, 67(1):55, 1960. URL: https://doi.org/10.2307/2308928.
  17. Daniel P. Sanders. On paths in planar graphs. J. Graph Theory, 24(4):341-345, 1997. URL: https://doi.org/10.1002/(SICI)1097-0118(199704)24:4<341::AID-JGT6>3.0.CO;2-O.
  18. Andreas Schmid and Jens M. Schmidt. Computing Tutte paths. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), volume 107 of LIPIcs, pages 98:1-98:14, 2018. URL: https://doi.org/10.4230/LIPIcs.ICALP.2018.98.
  19. William T. Tutte. A theorem on planar graphs. Trans. Amer. Math. Soc., 82(1):99-116, 1956. URL: https://doi.org/10.1090/S0002-9947-1956-0081471-8.
  20. Avi Wigderson. The complexity of the Hamiltonian circuit problem for maximal planar graphs. Technical Report 298, Princeton University, 1982. URL: http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/W82a/tech298.pdf.
  21. Mihalis Yannakakis. Four pages are necessary and sufficient for planar graphs (extended abstract). In Proc. 18th Annu. ACM Sympos. Theory Comput. (STOC 1986), pages 104-108, 1986. URL: https://doi.org/10.1145/12130.12141.
  22. Mihalis Yannakakis. Embedding planar graphs in four pages. J. Comput. Syst. Sci., 38(1):36-67, 1989. URL: https://doi.org/10.1016/0022-0000(89)90032-9.
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