Recognizing DAGs with Page-Number 2 is NP-complete Article Swipe
Michael A. Bekos
,
Giordano Da Lozzo
,
Fabrizio Frati
,
Martin Gronemann
,
Tamara Mchedlidze
,
Chrysanthi N. Raftopoulou
·
YOU?
·
· 2022
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2208.13615
YOU?
·
· 2022
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2208.13615
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\geq 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.
Related Topics
Metadata
- Type
- preprint
- Language
- en
- Landing Page
- http://arxiv.org/abs/2208.13615
- https://arxiv.org/pdf/2208.13615
- OA Status
- green
- Cited By
- 1
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W4294009593
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W4294009593Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.48550/arxiv.2208.13615Digital Object Identifier
- Title
-
Recognizing DAGs with Page-Number 2 is NP-completeWork title
- Type
-
preprintOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2022Year of publication
- Publication date
-
2022-08-29Full publication date if available
- Authors
-
Michael A. Bekos, Giordano Da Lozzo, Fabrizio Frati, Martin Gronemann, Tamara Mchedlidze, Chrysanthi N. RaftopoulouList of authors in order
- Landing page
-
https://arxiv.org/abs/2208.13615Publisher landing page
- PDF URL
-
https://arxiv.org/pdf/2208.13615Direct link to full text PDF
- Open access
-
YesWhether a free full text is available
- OA status
-
greenOpen access status per OpenAlex
- OA URL
-
https://arxiv.org/pdf/2208.13615Direct OA link when available
- Concepts
-
Directed acyclic graph, Combinatorics, Mathematics, Conjecture, Discrete mathematicsTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
1Total citation count in OpenAlex
- Citations by year (recent)
-
2022: 1Per-year citation counts (last 5 years)
- Related works (count)
-
10Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W4294009593 |
|---|---|
| doi | https://doi.org/10.48550/arxiv.2208.13615 |
| ids.doi | https://doi.org/10.48550/arxiv.2208.13615 |
| ids.openalex | https://openalex.org/W4294009593 |
| fwci | |
| type | preprint |
| title | Recognizing DAGs with Page-Number 2 is NP-complete |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | |
| topics[0].id | https://openalex.org/T10374 |
| topics[0].field.id | https://openalex.org/fields/17 |
| topics[0].field.display_name | Computer Science |
| topics[0].score | 0.9883999824523926 |
| topics[0].domain.id | https://openalex.org/domains/3 |
| topics[0].domain.display_name | Physical Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/1703 |
| topics[0].subfield.display_name | Computational Theory and Mathematics |
| topics[0].display_name | Advanced Graph Theory Research |
| topics[1].id | https://openalex.org/T10996 |
| topics[1].field.id | https://openalex.org/fields/17 |
| topics[1].field.display_name | Computer Science |
| topics[1].score | 0.9703999757766724 |
| topics[1].domain.id | https://openalex.org/domains/3 |
| topics[1].domain.display_name | Physical Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/1704 |
| topics[1].subfield.display_name | Computer Graphics and Computer-Aided Design |
| topics[1].display_name | Computational Geometry and Mesh Generation |
| topics[2].id | https://openalex.org/T12923 |
| topics[2].field.id | https://openalex.org/fields/17 |
| topics[2].field.display_name | Computer Science |
| topics[2].score | 0.9659000039100647 |
| topics[2].domain.id | https://openalex.org/domains/3 |
| topics[2].domain.display_name | Physical Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/1707 |
| topics[2].subfield.display_name | Computer Vision and Pattern Recognition |
| topics[2].display_name | Digital Image Processing Techniques |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C74197172 |
| concepts[0].level | 2 |
| concepts[0].score | 0.8606249094009399 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q1195339 |
| concepts[0].display_name | Directed acyclic graph |
| concepts[1].id | https://openalex.org/C114614502 |
| concepts[1].level | 1 |
| concepts[1].score | 0.7945635318756104 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q76592 |
| concepts[1].display_name | Combinatorics |
| concepts[2].id | https://openalex.org/C33923547 |
| concepts[2].level | 0 |
| concepts[2].score | 0.5867083072662354 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[2].display_name | Mathematics |
| concepts[3].id | https://openalex.org/C2780990831 |
| concepts[3].level | 2 |
| concepts[3].score | 0.5617290139198303 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q319141 |
| concepts[3].display_name | Conjecture |
| concepts[4].id | https://openalex.org/C118615104 |
| concepts[4].level | 1 |
| concepts[4].score | 0.45593327283859253 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q121416 |
| concepts[4].display_name | Discrete mathematics |
| keywords[0].id | https://openalex.org/keywords/directed-acyclic-graph |
| keywords[0].score | 0.8606249094009399 |
| keywords[0].display_name | Directed acyclic graph |
| keywords[1].id | https://openalex.org/keywords/combinatorics |
| keywords[1].score | 0.7945635318756104 |
| keywords[1].display_name | Combinatorics |
| keywords[2].id | https://openalex.org/keywords/mathematics |
| keywords[2].score | 0.5867083072662354 |
| keywords[2].display_name | Mathematics |
| keywords[3].id | https://openalex.org/keywords/conjecture |
| keywords[3].score | 0.5617290139198303 |
| keywords[3].display_name | Conjecture |
| keywords[4].id | https://openalex.org/keywords/discrete-mathematics |
| keywords[4].score | 0.45593327283859253 |
| keywords[4].display_name | Discrete mathematics |
| language | en |
| locations[0].id | pmh:oai:arXiv.org:2208.13615 |
| locations[0].is_oa | True |
| locations[0].source.id | https://openalex.org/S4306400194 |
| locations[0].source.issn | |
| locations[0].source.type | repository |
| locations[0].source.is_oa | True |
| locations[0].source.issn_l | |
| locations[0].source.is_core | False |
| locations[0].source.is_in_doaj | False |
| locations[0].source.display_name | arXiv (Cornell University) |
| locations[0].source.host_organization | https://openalex.org/I205783295 |
| locations[0].source.host_organization_name | Cornell University |
| locations[0].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[0].license | |
| locations[0].pdf_url | https://arxiv.org/pdf/2208.13615 |
| locations[0].version | submittedVersion |
| locations[0].raw_type | |
| locations[0].license_id | |
| locations[0].is_accepted | False |
| locations[0].is_published | False |
| locations[0].raw_source_name | |
| locations[0].landing_page_url | http://arxiv.org/abs/2208.13615 |
| locations[1].id | doi:10.48550/arxiv.2208.13615 |
| locations[1].is_oa | True |
| locations[1].source.id | https://openalex.org/S4306400194 |
| locations[1].source.issn | |
| locations[1].source.type | repository |
| locations[1].source.is_oa | True |
| locations[1].source.issn_l | |
| locations[1].source.is_core | False |
| locations[1].source.is_in_doaj | False |
| locations[1].source.display_name | arXiv (Cornell University) |
| locations[1].source.host_organization | https://openalex.org/I205783295 |
| locations[1].source.host_organization_name | Cornell University |
| locations[1].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[1].license | |
| locations[1].pdf_url | |
| locations[1].version | |
| locations[1].raw_type | article |
| locations[1].license_id | |
| locations[1].is_accepted | False |
| locations[1].is_published | |
| locations[1].raw_source_name | |
| locations[1].landing_page_url | https://doi.org/10.48550/arxiv.2208.13615 |
| indexed_in | arxiv, datacite |
| authorships[0].author.id | https://openalex.org/A5006472576 |
| authorships[0].author.orcid | https://orcid.org/0000-0002-3414-7444 |
| authorships[0].author.display_name | Michael A. Bekos |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Bekos, Michael A. |
| authorships[0].is_corresponding | False |
| authorships[1].author.id | https://openalex.org/A5006893407 |
| authorships[1].author.orcid | https://orcid.org/0000-0003-2396-5174 |
| authorships[1].author.display_name | Giordano Da Lozzo |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | Da Lozzo, Giordano |
| authorships[1].is_corresponding | False |
| authorships[2].author.id | https://openalex.org/A5025842302 |
| authorships[2].author.orcid | https://orcid.org/0000-0001-5987-8713 |
| authorships[2].author.display_name | Fabrizio Frati |
| authorships[2].author_position | middle |
| authorships[2].raw_author_name | Frati, Fabrizio |
| authorships[2].is_corresponding | False |
| authorships[3].author.id | https://openalex.org/A5080178526 |
| authorships[3].author.orcid | https://orcid.org/0000-0003-2565-090X |
| authorships[3].author.display_name | Martin Gronemann |
| authorships[3].author_position | middle |
| authorships[3].raw_author_name | Gronemann, Martin |
| authorships[3].is_corresponding | False |
| authorships[4].author.id | https://openalex.org/A5037539653 |
| authorships[4].author.orcid | https://orcid.org/0000-0001-6249-3419 |
| authorships[4].author.display_name | Tamara Mchedlidze |
| authorships[4].author_position | middle |
| authorships[4].raw_author_name | Mchedlidze, Tamara |
| authorships[4].is_corresponding | False |
| authorships[5].author.id | https://openalex.org/A5056184296 |
| authorships[5].author.orcid | https://orcid.org/0000-0001-6457-516X |
| authorships[5].author.display_name | Chrysanthi N. Raftopoulou |
| authorships[5].author_position | last |
| authorships[5].raw_author_name | Raftopoulou, Chrysanthi N. |
| authorships[5].is_corresponding | False |
| has_content.pdf | False |
| has_content.grobid_xml | False |
| is_paratext | False |
| open_access.is_oa | True |
| open_access.oa_url | https://arxiv.org/pdf/2208.13615 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-10-10T00:00:00 |
| display_name | Recognizing DAGs with Page-Number 2 is NP-complete |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-06T06:51:31.235846 |
| primary_topic.id | https://openalex.org/T10374 |
| primary_topic.field.id | https://openalex.org/fields/17 |
| primary_topic.field.display_name | Computer Science |
| primary_topic.score | 0.9883999824523926 |
| primary_topic.domain.id | https://openalex.org/domains/3 |
| primary_topic.domain.display_name | Physical Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/1703 |
| primary_topic.subfield.display_name | Computational Theory and Mathematics |
| primary_topic.display_name | Advanced Graph Theory Research |
| related_works | https://openalex.org/W4391375266, https://openalex.org/W1979597421, https://openalex.org/W2007980826, https://openalex.org/W2061531152, https://openalex.org/W4302345037, https://openalex.org/W3002753104, https://openalex.org/W2077600819, https://openalex.org/W2142036596, https://openalex.org/W2072657027, https://openalex.org/W4297794376 |
| cited_by_count | 1 |
| counts_by_year[0].year | 2022 |
| counts_by_year[0].cited_by_count | 1 |
| locations_count | 2 |
| best_oa_location.id | pmh:oai:arXiv.org:2208.13615 |
| best_oa_location.is_oa | True |
| best_oa_location.source.id | https://openalex.org/S4306400194 |
| best_oa_location.source.issn | |
| best_oa_location.source.type | repository |
| best_oa_location.source.is_oa | True |
| best_oa_location.source.issn_l | |
| best_oa_location.source.is_core | False |
| best_oa_location.source.is_in_doaj | False |
| best_oa_location.source.display_name | arXiv (Cornell University) |
| best_oa_location.source.host_organization | https://openalex.org/I205783295 |
| best_oa_location.source.host_organization_name | Cornell University |
| best_oa_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| best_oa_location.license | |
| best_oa_location.pdf_url | https://arxiv.org/pdf/2208.13615 |
| best_oa_location.version | submittedVersion |
| best_oa_location.raw_type | |
| best_oa_location.license_id | |
| best_oa_location.is_accepted | False |
| best_oa_location.is_published | False |
| best_oa_location.raw_source_name | |
| best_oa_location.landing_page_url | http://arxiv.org/abs/2208.13615 |
| primary_location.id | pmh:oai:arXiv.org:2208.13615 |
| primary_location.is_oa | True |
| primary_location.source.id | https://openalex.org/S4306400194 |
| primary_location.source.issn | |
| primary_location.source.type | repository |
| primary_location.source.is_oa | True |
| primary_location.source.issn_l | |
| primary_location.source.is_core | False |
| primary_location.source.is_in_doaj | False |
| primary_location.source.display_name | arXiv (Cornell University) |
| primary_location.source.host_organization | https://openalex.org/I205783295 |
| primary_location.source.host_organization_name | Cornell University |
| primary_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| primary_location.license | |
| primary_location.pdf_url | https://arxiv.org/pdf/2208.13615 |
| primary_location.version | submittedVersion |
| primary_location.raw_type | |
| primary_location.license_id | |
| primary_location.is_accepted | False |
| primary_location.is_published | False |
| primary_location.raw_source_name | |
| primary_location.landing_page_url | http://arxiv.org/abs/2208.13615 |
| publication_date | 2022-08-29 |
| publication_year | 2022 |
| referenced_works_count | 0 |
| abstract_inverted_index.a | 3, 20, 24 |
| abstract_inverted_index.(a | 7 |
| abstract_inverted_index.3$ | 97 |
| abstract_inverted_index.In | 47, 100, 113 |
| abstract_inverted_index.J. | 74 |
| abstract_inverted_index.by | 84 |
| abstract_inverted_index.et | 78 |
| abstract_inverted_index.in | 110 |
| abstract_inverted_index.is | 11, 61, 71, 92 |
| abstract_inverted_index.no | 31 |
| abstract_inverted_index.of | 2, 26, 34, 56 |
| abstract_inverted_index.we | 103 |
| abstract_inverted_index.$2$ | 60 |
| abstract_inverted_index.$6$ | 70 |
| abstract_inverted_index.$k$ | 14, 91 |
| abstract_inverted_index.DAG | 18 |
| abstract_inverted_index.The | 0 |
| abstract_inverted_index.al. | 79 |
| abstract_inverted_index.and | 23, 50, 63, 107, 123 |
| abstract_inverted_index.for | 9, 15, 94, 120 |
| abstract_inverted_index.has | 19 |
| abstract_inverted_index.its | 27 |
| abstract_inverted_index.our | 115 |
| abstract_inverted_index.the | 12, 17, 35, 44, 54, 111 |
| abstract_inverted_index.two | 32 |
| abstract_inverted_index.DAG, | 8 |
| abstract_inverted_index.DAGs | 57, 67, 88 |
| abstract_inverted_index.even | 119 |
| abstract_inverted_index.have | 40 |
| abstract_inverted_index.same | 36 |
| abstract_inverted_index.such | 29 |
| abstract_inverted_index.that | 30, 53, 65, 86 |
| abstract_inverted_index.this | 82, 101 |
| abstract_inverted_index.with | 58, 68, 89 |
| abstract_inverted_index.1999, | 48 |
| abstract_inverted_index.Heath | 49, 106 |
| abstract_inverted_index.[SIAM | 73 |
| abstract_inverted_index.[SoCG | 98 |
| abstract_inverted_index.along | 43 |
| abstract_inverted_index.color | 37 |
| abstract_inverted_index.edges | 28, 33 |
| abstract_inverted_index.every | 95 |
| abstract_inverted_index.graph | 6 |
| abstract_inverted_index.holds | 118 |
| abstract_inverted_index.i.e., | 39 |
| abstract_inverted_index.order | 22 |
| abstract_inverted_index.which | 16 |
| abstract_inverted_index.$k\geq | 96 |
| abstract_inverted_index.1999]. | 76 |
| abstract_inverted_index.2019]. | 99 |
| abstract_inverted_index.cross, | 38 |
| abstract_inverted_index.graphs | 122 |
| abstract_inverted_index.order. | 46 |
| abstract_inverted_index.paper, | 102 |
| abstract_inverted_index.planar | 124 |
| abstract_inverted_index.proved | 64 |
| abstract_inverted_index.result | 83, 117 |
| abstract_inverted_index.short) | 10 |
| abstract_inverted_index.Binucci | 77 |
| abstract_inverted_index.acyclic | 5 |
| abstract_inverted_index.finally | 104 |
| abstract_inverted_index.minimum | 13 |
| abstract_inverted_index.posets. | 125 |
| abstract_inverted_index.proving | 85 |
| abstract_inverted_index.resolve | 105 |
| abstract_inverted_index.directed | 4 |
| abstract_inverted_index.recently | 80 |
| abstract_inverted_index.Pemmaraju | 51 |
| abstract_inverted_index.endpoints | 42 |
| abstract_inverted_index.Computing, | 75 |
| abstract_inverted_index.conjecture | 109 |
| abstract_inverted_index.$st$-planar | 121 |
| abstract_inverted_index.NP-complete | 62, 72 |
| abstract_inverted_index.Pemmaraju's | 108 |
| abstract_inverted_index.alternating | 41 |
| abstract_inverted_index.conjectured | 52 |
| abstract_inverted_index.page-number | 1, 59, 69, 90 |
| abstract_inverted_index.particular, | 114 |
| abstract_inverted_index.recognition | 55 |
| abstract_inverted_index.recognizing | 66, 87 |
| abstract_inverted_index.topological | 21, 45 |
| abstract_inverted_index.$k$-coloring | 25 |
| abstract_inverted_index.NP-complete, | 93 |
| abstract_inverted_index.affirmative. | 112 |
| abstract_inverted_index.strengthened | 81 |
| abstract_inverted_index.NP-completeness | 116 |
| cited_by_percentile_year | |
| countries_distinct_count | 0 |
| institutions_distinct_count | 6 |
| citation_normalized_percentile |