2014/01/03 by Michael A. Bekos, Bekos, Michael A., Martin Gronemann +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithms and Data Compression #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Computational Geometry and Mesh Generation #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.CC #cs.DM #math.CO
paper · pdf · doi:10.48550/arxiv.1401.0684
21 pages, 16 Figures. A shorter version is to appear at STACS 2014
arxiv created 2014/01/03 · openalex publication_date 2014/01/03 · arxiv updated 2014/01/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.