On the upward book thickness problem: combinatorial and complexity results

DOI10.1016/j.ejc.2022.103662OpenAlexW4312002273MaRDI QIDQ5925712

Martin Nöllenburg, Fabrizio Montecchiani, Sujoy Bhore, Giordano Da Lozzo

Publication date: 27 April 2023

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejc.2022.103662

zbMATH Keywords

book embeddinggraph embeddingdagsdirected acyclic graphsforbidden subgraphqueue layoutstack layout

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (2)

Upward book embeddability of \(st\)-graphs: complexity and algorithms ⋮ Recognizing DAGs with page-number 2 is NP-complete

Cites Work

• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Improved upper bounds for vertex cover
• On miniaturized problems in parameterized complexity theory
• Ordered sets, pagenumbers and planarity
• Embedding planar graphs in four pages
• Algorithms for plane representations of acyclic digraphs
• The book thickness of a graph
• Planar graphs that need four pages
• On the number of upward planar orientations of maximal planar graphs
• Advancements on SEFE and partitioned book embedding problems
• Graph treewidth and geometric thickness parameters
• Computing straight-line 3D grid drawings of graphs in linear volume
• The book thickness of 1-planar graphs is constant
• Book embeddability of series-parallel digraphs
• Upward Planarity Testing in Practice
• Upward Spirality and Upward Planarity Testing
• Crossing-Free Acyclic Hamiltonian Path Completion for Planar st-Digraphs
• Comparing Queues and Stacks As Machines for Laying Out Graphs
• Stack and Queue Layouts of Directed Acyclic Graphs: Part I
• Stack and Queue Layouts of Directed Acyclic Graphs: Part II
• Genus g Graphs Have Pagenumber O(√g)
• Stack and Queue Layouts of Posets
• Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design
• On the Page Number of Upward Planar Directed Acyclic Graphs
• Circle graphs are quadratically χ‐bounded
• Atomic Embeddability, Clustered Planarity, and Thickenability
• Upward Book Embeddings of st-Graphs
• Four pages are indeed necessary for planar graphs
• Parameterized Algorithms for Book Embedding Problems
• Layout of Graphs with Bounded Tree-Width
• Parameterized Algorithms
• Sorting Using Networks of Queues and Stacks
• Extending upward planar graph drawings
• Upward planar morphs
• Book embeddings of nonplanar graphs with small faces in few pages

This page was built for publication: On the upward book thickness problem: combinatorial and complexity results