Two-page book embeddings of 4-planar graphs

DOI10.1007/s00453-015-0016-8zbMath1339.05066OpenAlexW2100223096MaRDI QIDQ300468

Michael A. Bekos, Chrysanthi N. Raftopoulou, Martin Gronemann

Publication date: 28 June 2016

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2014/4453/

zbMATH Keywords

4-planar graphsbook-embeddingsub-Hamiltonian graph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Eulerian and Hamiltonian graphs (05C45) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (18)

A survey on book-embedding of planar graphs ⋮ Parameterized algorithms for linear layouts of graphs with respect to the vertex cover number ⋮ Embedding planar 5-graphs in three pages ⋮ Upward book embeddability of \(st\)-graphs: complexity and algorithms ⋮ Gamma deployment problem in grids: hardness and new integer linear programming formulation ⋮ Book embeddings of \(k\)-framed graphs and \(k\)-map graphs ⋮ Recognizing DAGs with page-number 2 is NP-complete ⋮ The Rique-number of graphs ⋮ Colored anchored visibility representations in 2D and 3D space ⋮ Parameterized algorithms for book embedding problems ⋮ Upward Partitioned Book Embeddings ⋮ Parameterized Algorithms for Book Embedding Problems ⋮ Unnamed Item ⋮ On dispersable book embeddings ⋮ Recognizing DAGs with page-number 2 is NP-complete ⋮ Upward Book Embeddings of st-Graphs ⋮ On mixed linear layouts of series-parallel graphs ⋮ On Mixed Linear Layouts of Series-Parallel Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Embedding planar graphs in four pages
• The book thickness of a graph
• Any maximal planar graph with only one separating triangle is Hamiltonian
• A theorem on graphs
• Each maximal planar graph with exactly two separating triangles is Hamiltonian
• Extension of a theorem of Whitney
• The hamiltonian cycle problem is linear-time solvable for 4-connected planar graphs
• A Theorem on Planar Graphs
• Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design

This page was built for publication: Two-page book embeddings of 4-planar graphs