On the upward book thickness problem: combinatorial and complexity results

DOI10.1007/978-3-030-92931-2_18OpenAlexW3197114469MaRDI QIDQ5918733

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

Publication date: 1 July 2022

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2108.12327

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (3)

Parameterized Algorithms for Queue Layouts ⋮ A Sublinear Bound on the Page Number of Upward Planar Graphs ⋮ Recognizing DAGs with page-number 2 is NP-complete

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved upper bounds for vertex cover
• Ordered sets, pagenumbers and planarity
• Embedding planar graphs in four pages
• Algorithms for plane representations of acyclic digraphs
• The book thickness of a graph
• Advancements on SEFE and partitioned book embedding problems
• Graph treewidth and geometric thickness parameters
• The book thickness of 1-planar graphs is constant
• Book embeddability of series-parallel digraphs
• Crossing-Optimal Acyclic Hamiltonian Path Completion and Its Application to Upward Topological Book Embeddings
• 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
• Upward Book Embeddings of st-Graphs
• Four pages are indeed necessary for planar graphs
• Parameterized Algorithms for Book Embedding Problems
• Atomic Embeddability, Clustered Planarity, and Thickenability
• 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