Recognizing DAGs with page-number 2 is NP-complete

DOI10.1007/978-3-031-22203-0_26arXiv2208.13615OpenAlexW4317393684MaRDI QIDQ6117080

Martin Gronemann, Tamara Mchedlidze, Fabrizio Frati, Giordano Da Lozzo, Michael A. Bekos, Chrysanthi N. Raftopoulou

Publication date: 16 August 2023

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

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

zbMATH Keywords

directed acyclic graphsplanar posetspage-number

Mathematics Subject Classification ID

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

Related Items (2)

A Sublinear Bound on the Page Number of Upward Planar Graphs ⋮ Upward book embeddability of \(st\)-graphs: complexity and algorithms

Cites Work

• Unnamed Item
• Two-page book embeddings of 4-planar graphs
• Ordered sets, pagenumbers and planarity
• Fundamentals of planar ordered sets
• Embedding planar graphs in four pages
• Algorithms for plane representations of acyclic digraphs
• A left-first search algorithm for planar graphs
• Embedding planar 5-graphs in three pages
• Planar graphs that need four pages
• Hamiltonian circuits in simplicial complexes
• Extension of a theorem of Whitney
• Book embeddability of series-parallel digraphs
• Recognizing DAGs with page-number 2 is NP-complete
• Crossing-Optimal Acyclic HP-Completion for Outerplanar st-Digraphs
• Crossing-Optimal Acyclic Hamiltonian Path Completion and Its Application to Upward Topological Book Embeddings
• Embedding Outerplanar Graphs in Small Books
• Stack and Queue Layouts of Directed Acyclic Graphs: Part I
• Stack and Queue Layouts of Directed Acyclic Graphs: Part II
• Halin graphs and the travelling salesman problem
• On the Page Number of Upward Planar Directed Acyclic Graphs
• Upward Book Embeddings of st-Graphs
• Four pages are indeed necessary for planar graphs
• OPTIMAL BINARY SPACE PARTITIONS FOR SEGMENTS IN THE PLANE
• On the upward book thickness problem: combinatorial and complexity results
• Stack and queue number of 2-trees

This page was built for publication: Recognizing DAGs with page-number 2 is NP-complete