Two-Page Book Embeddings of 4-Planar Graphs (Extended Draft Version)

Bekos, Michael A. and Gronemann, Martin and Raftopoulou, Chrysanthi N. (2014) Two-Page Book Embeddings of 4-Planar Graphs (Extended Draft Version).
Technical Report , 21 p.

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.


Actions:
Full text not available from this repository.
Editorial actions: View Item View Item (Login required)
Content information:
Item Type: Paper (Technical Report)
Citations: No citation data.
Uncontrolled Keywords:
Subjects:
  • 68-XX Computer science > 68Wxx Algorithms

    		•
    Divisions: Institute of Computer Science > Computer Science Department - Prof. Dr. Juenger
    Related URLs:
    Deposit Information:
    ZAIK Number: UNSPECIFIED
    Depositing User: Martin Gronemann
    Date Deposited: 11 Jun 2014 11:25
    Last Modified: 16 Jun 2014 13:25
    URI: http://e-archive.informatik.uni-koeln.de/id/eprint/802