Recognizing DAGs with Page-Number 2 Is NP-complete

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

doi:10.1007/978-3-031-22203-0_26

Recognizing DAGs with Page-Number 2 Is NP-complete

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

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.

Original language	English
Title of host publication	Graph Drawing and Network Visualization - 30th International Symposium, GD 2022, Tokyo, Japan, September 13-16, 2022, Revised Selected Papers
Editors	Patrizio Angelini, Reinhard von Hanxleden
Publisher	Springer
Pages	361-370
Number of pages	10
Volume	13764
DOIs	https://doi.org/10.1007/978-3-031-22203-0_26
Publication status	Published - 2022

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer

Access to Document

10.1007/978-3-031-22203-0_26

978-3-031-22203-0_26Final published version, 376 KBLicence: Taverne

Cite this

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, pp. 361-370). (Lecture Notes in Computer Science). Springer. https://doi.org/10.1007/978-3-031-22203-0_26

Bekos, Michael A. ; Lozzo, Giordano Da ; Frati, Fabrizio et al. / Recognizing DAGs with Page-Number 2 Is NP-complete. Graph Drawing and Network Visualization - 30th International Symposium, GD 2022, Tokyo, Japan, September 13-16, 2022, Revised Selected Papers. editor / Patrizio Angelini ; Reinhard von Hanxleden. Vol. 13764 Springer, 2022. pp. 361-370 (Lecture Notes in Computer Science).

@inproceedings{ae858fa62748447fa7e6adff1bd96057,

title = "Recognizing DAGs with Page-Number 2 Is NP-complete",

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{\textquoteright}s conjecture in the affirmative. In particular, our NP-completeness result holds even for st-planar graphs and planar posets.",

author = "Bekos, {Michael A.} and Lozzo, {Giordano Da} and Fabrizio Frati and Martin Gronemann and Tamara Mchedlidze and Raftopoulou, {Chrysanthi N.}",

year = "2022",

doi = "10.1007/978-3-031-22203-0_26",

language = "English",

volume = "13764",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "361--370",

editor = "Patrizio Angelini and Hanxleden, {Reinhard von}",

booktitle = "Graph Drawing and Network Visualization - 30th International Symposium, GD 2022, Tokyo, Japan, September 13-16, 2022, Revised Selected Papers",

}

Bekos, MA, Lozzo, GD, Frati, F, Gronemann, M, Mchedlidze, T & Raftopoulou, CN 2022, Recognizing DAGs with Page-Number 2 Is NP-complete. in P Angelini & RV 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

Recognizing DAGs with Page-Number 2 Is NP-complete. / Bekos, Michael A.; Lozzo, Giordano Da; Frati, Fabrizio et al.
Graph Drawing and Network Visualization - 30th International Symposium, GD 2022, Tokyo, Japan, September 13-16, 2022, Revised Selected Papers. ed. / Patrizio Angelini; Reinhard von Hanxleden. Vol. 13764 Springer, 2022. p. 361-370 (Lecture Notes in Computer Science).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Recognizing DAGs with Page-Number 2 Is NP-complete

AU - Bekos, Michael A.

AU - Lozzo, Giordano Da

AU - Frati, Fabrizio

AU - Gronemann, Martin

AU - Mchedlidze, Tamara

AU - Raftopoulou, Chrysanthi N.

PY - 2022

Y1 - 2022

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-031-22203-0_26

DO - 10.1007/978-3-031-22203-0_26

M3 - Conference contribution

VL - 13764

T3 - Lecture Notes in Computer Science

SP - 361

EP - 370

BT - Graph Drawing and Network Visualization - 30th International Symposium, GD 2022, Tokyo, Japan, September 13-16, 2022, Revised Selected Papers

A2 - Angelini, Patrizio

A2 - Hanxleden, Reinhard von

PB - Springer

ER -

Bekos MA, Lozzo GD, Frati F, Gronemann M, Mchedlidze T, Raftopoulou CN. Recognizing DAGs with Page-Number 2 Is NP-complete. In Angelini P, Hanxleden RV, editors, Graph Drawing and Network Visualization - 30th International Symposium, GD 2022, Tokyo, Japan, September 13-16, 2022, Revised Selected Papers. Vol. 13764. Springer. 2022. p. 361-370. (Lecture Notes in Computer Science). doi: 10.1007/978-3-031-22203-0_26

Recognizing DAGs with Page-Number 2 Is NP-complete

Abstract

Publication series

Access to Document

Fingerprint

Cite this