Hoffmann, Michael ;
Klemz, Boris
Triconnected Planar Graphs of Maximum Degree Five are Subhamiltonian
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 2page 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 3connected 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.
BibTeX  Entry
@InProceedings{hoffmann_et_al:LIPIcs:2019:11179,
author = {Michael Hoffmann and Boris Klemz},
title = {{Triconnected Planar Graphs of Maximum Degree Five are Subhamiltonian}},
booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)},
pages = {58:158:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771245},
ISSN = {18688969},
year = {2019},
volume = {144},
editor = {Michael A. Bender and Ola Svensson and Grzegorz Herman},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11179},
URN = {urn:nbn:de:0030drops111797},
doi = {10.4230/LIPIcs.ESA.2019.58},
annote = {Keywords: Graph drawing, book embedding, Hamiltonian graph, planar graph, bounded degree graph, graph augmentation, computational geometry, SPQR decomposition}
}
06.09.2019
Keywords: 

Graph drawing, book embedding, Hamiltonian graph, planar graph, bounded degree graph, graph augmentation, computational geometry, SPQR decomposition 
Seminar: 

27th Annual European Symposium on Algorithms (ESA 2019)

Issue date: 

2019 
Date of publication: 

06.09.2019 