文章基本信息

标题：Two-Page Book Embeddings of 4-Planar Graphs
本地全文：下载
作者：Michael A. Bekos ; Martin Gronemann ; Chrysanthi N. Raftopoulou 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2014
卷号：25
页码：137-148
DOI：10.4230/LIPIcs.STACS.2014.137
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Book Embedding; Subhamiltonicity; 4-Planar Graphs