Open access
Datum
2019Typ
- Conference Paper
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. Mehr anzeigen
Persistenter Link
https://doi.org/10.3929/ethz-b-000378782Publikationsstatus
publishedExterne Links
Buchtitel
27th Annual European Symposium on Algorithms (ESA 2019)Zeitschrift / Serie
Leibniz International Proceedings in Informatics (LIPIcs)Band
Seiten / Artikelnummer
Verlag
Schloss Dagstuhl - Leibniz-Zentrum für InformatikKonferenz
Thema
Graph drawing; Book embedding; Hamiltonian graph; Planar graph; Bounded degree graph; Graph augmentation; Computational geometry; SPQR decompositionOrganisationseinheit
03457 - Welzl, Emo (emeritus) / Welzl, Emo (emeritus)
Förderung
171681 - Arrangements and Drawings (ArrDra) (SNF)