2022/08/29 by Michael A. Bekos, Giordano Da Lozzo, Bekos, Michael A. +9 · 1 citation
Computer Science · #Advanced Graph Theory Research #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #Digital Image Processing Techniques #FOS: Computer and information sciences #cs.CG #cs.DS
paper · pdf · doi:10.48550/arxiv.2208.13615
Appears in the Proceedings of the 30th International Symposium on Graph Drawing and Network Visualization (GD 2022)
openalex publication_date 2022/08/29 · arxiv created 2022/11/11 · arxiv updated 2022/11/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The page-number of a directed acyclic graph (a DAG, for short) is the minimum k for which the DAG has a topological order and a k-coloring of its edges such that no two edges of the same color cross, i.e., have alternating endpoints along the topological order. In 1999, Heath and Pemmaraju conjectured that the recognition of DAGs with page-number 2 is NP-complete and proved that recognizing DAGs with page-number 6 is NP-complete [SIAM J. Computing, 1999]. Binucci et al. recently strengthened this result by proving that recognizing DAGs with page-number k is NP-complete, for every k≥ 3 [SoCG 2019]. In this paper, we finally resolve Heath and Pemmaraju's conjecture in the affirmative. In particular, our NP-completeness result holds even for st-planar graphs and planar posets.