Two-page book embeddings of 4-planar graphs
From MaRDI portal
Publication:300468
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/
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
