Universität zu Köln

Bekos, Michael A. ORCID: 0000-0002-3414-7444, Gronemann, Martin ORCID: 0000-0003-2565-090X and Raftopoulou, Chrysanthi N. (2016). Two-Page Book Embeddings of 4-Planar Graphs. Algorithmica, 75 (1). S. 158 - 186. NEW YORK: SPRINGER. ISSN 1432-0541

Full text not available from this repository.

Abstract

Back in the eighties, Heath [Algorithms for embedding graphs in books. PhD thesis, University of North Carolina, Chapel Hill, 1985] 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.

Item Type:	Journal Article
Creators:	Creators Email ORCID ORCID Put Code Bekos, Michael A. UNSPECIFIED orcid.org/0000-0002-3414-7444 UNSPECIFIED Gronemann, Martin UNSPECIFIED orcid.org/0000-0003-2565-090X UNSPECIFIED Raftopoulou, Chrysanthi N. UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-277143
DOI:	10.1007/s00453-015-0016-8
Journal or Publication Title:	Algorithmica
Volume:	75
Number:	1
Page Range:	S. 158 - 186
Date:	2016
Publisher:	SPRINGER
Place of Publication:	NEW YORK
ISSN:	1432-0541
Language:	English
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects:	Data processing Computer science
Uncontrolled Keywords:	Keywords Language MAXIMAL PLANAR GRAPH Multiple languages Computer Science, Software Engineering; Mathematics, Applied Multiple languages
Refereed:	Yes
URI:	http://kups.ub.uni-koeln.de/id/eprint/27714