Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2014.137
URN: urn:nbn:de:0030-drops-44536
URL: https://drops.dagstuhl.de/opus/volltexte/2014/4453/
Bekos, Michael A. ; Gronemann, Martin ; Raftopoulou, Chrysanthi N.
Two-Page Book Embeddings of 4-Planar Graphs
| pdf-format: |
|
Abstract
Back in the eighties, Heath showed that every 3-planar graph is subhamiltonian and asked whether this result can be extended to a class of graphs of degree greater than three. In this paper we affirmatively answer this question for the class of 4-planar graphs. Our contribution consists of two algorithms: The first one is limited to triconnected graphs, but runs in linear time and uses existing methods for computing hamiltonian cycles in planar graphs. The second one, which solves the general case of the problem, is a quadratic-time algorithm based on the book embedding viewpoint of the problem.
BibTeX - Entry
@InProceedings{bekos_et_al:LIPIcs:2014:4453,
author = {Michael A. Bekos and Martin Gronemann and Chrysanthi N. Raftopoulou},
title = {{Two-Page Book Embeddings of 4-Planar Graphs}},
booktitle = {31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
pages = {137--148},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-65-1},
ISSN = {1868-8969},
year = {2014},
volume = {25},
editor = {Ernst W. Mayr and Natacha Portier},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2014/4453},
URN = {urn:nbn:de:0030-drops-44536},
doi = {10.4230/LIPIcs.STACS.2014.137},
annote = {Keywords: Book Embedding, Subhamiltonicity, 4-Planar Graphs}
}
| Keywords: | Book Embedding, Subhamiltonicity, 4-Planar Graphs | |
| Seminar: | 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014) | |
| Issue date: | 2014 | |
| Date of publication: | 05.03.2014 |
