<script type="text/javascript">
<!--
document.write('<div id="oa_widget"></div>');
document.write('<script type="text/javascript" src="https://www.openaire.eu/index.php?option=com_openaire&view=widget&format=raw&projectId=undefined&type=result"></script>');
-->
</script>

COPY SCRIPT

For further information contact us at helpdesk@openaire.eu

Two-Page Book Embeddings of 4-Planar Graphs

descriptionPublicationkeyboard_double_arrow_right Article , Preprint , Conference object 16 Jun 2015Embargo end date: 01 Jan 2014 Germany English Publisher:Springer Science and Business Media LLCJournal:Algorithmica, volume 75, pages 158-185 (issn: 0178-4617, eissn: 1432-0541,

Authors: Bekos, Michael A.; Gronemann, Martin; Raftopoulou, Chrysanthi N.;

doi: 10.1007/s00453-015-0016-8 , 10.48550/arxiv.1401.0684 , 10.4230/lipics.stacs.2014.137

arXiv: http://arxiv.org/abs/1401.0684

Two-Page Book Embeddings of 4-Planar Graphs

- Summary
- Subjects
- Related research
  (1)
- Metrics

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.

21 pages, 16 Figures. A shorter version is to appear at STACS 2014

Country

Germany

Related Organizations

View all View all

Keywords

FOS: Computer and information sciences, Discrete Mathematics (cs.DM), Computational Complexity (cs.CC), 004, Book Embedding, Computer Science - Computational Complexity, FOS: Mathematics, Mathematics - Combinatorics, 4-Planar Graphs, Combinatorics (math.CO), Subhamiltonicity, Computer Science - Discrete Mathematics, ddc: ddc:004

1 Research products, page of 1

Impact byBIP!

	citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	20
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Top 10%
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Top 10%
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Top 10%

Found an issue? Give us feedback

Top 10%

Green

hybrid

Beta

SDGs Suggest

16. Peace & justice

Beta

SDGs:

16. Peace & justice,

Related to Research communities

Knowmad Institut