Recognizing DAGs with Page-Number 2 Is NP-complete
Publication date
2022
Authors
Bekos, Michael A.
Lozzo, Giordano Da
Frati, Fabrizio
Gronemann, Martin
Mchedlidze, Tamara
Raftopoulou, Chrysanthi N.
Editors
Angelini, Patrizio
Hanxleden, Reinhard von
Advisors
Supervisors
Document Type
Part of book
Metadata
Show full item recordCollections
License
taverne
Abstract
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.
Keywords
Taverne
Citation
Bekos, M A, Lozzo, G D, Frati, F, Gronemann, M, Mchedlidze, T & Raftopoulou, C N 2022, Recognizing DAGs with Page-Number 2 Is NP-complete. in P Angelini & R V Hanxleden (eds), Graph Drawing and Network Visualization - 30th International Symposium, GD 2022, Tokyo, Japan, September 13-16, 2022, Revised Selected Papers. vol. 13764, Lecture Notes in Computer Science, Springer, pp. 361-370. https://doi.org/10.1007/978-3-031-22203-0_26