Bitonic st-Orderings for Upward Planar Graphs: Splits and Bends in the Variable Embedding Scenario Article Swipe
Patrizio Angelini
,
Michael A. Bekos
,
Henry Förster
,
Martin Gronemann
·
YOU?
·
· 2023
· Open Access
·
· DOI: https://doi.org/10.1007/s00453-023-01111-5
YOU?
·
· 2023
· Open Access
·
· DOI: https://doi.org/10.1007/s00453-023-01111-5
Bitonic st -orderings for st -planar graphs were introduced as a method to cope with several graph drawing problems. Notably, they have been used to obtain the best-known upper bound on the number of bends for upward planar polyline drawings with at most one bend per edge in polynomial area. For an st -planar graph that does not admit a bitonic st -ordering, one may split certain edges such that for the resulting graph such an ordering exists. Since each split is interpreted as a bend, one is usually interested in splitting as few edges as possible. While this optimization problem admits a linear-time algorithm in the fixed embedding setting, it remains open in the variable embedding setting. We close this gap in the literature by providing a linear-time algorithm that optimizes over all embeddings of the input st -planar graph. The best-known lower bound on the number of required splits of an st -planar graph with n vertices is $$n-3$$ . However, it is possible to compute a bitonic st -ordering without any split for the st -planar graph obtained by reversing the orientation of all edges. In terms of upward planar polyline drawings in polynomial area, the former translates into $$n-3$$ bends, while the latter into no bends. We show that this idea cannot always be exploited by describing an st -planar graph that needs at least $$n-5$$ splits in both orientations. We provide analogous bounds for graphs with small degree. Finally, we further investigate the relationship between splits in bitonic st-orderings and bends in upward planar polyline drawings with polynomial area, by providing bounds on the number of bends in such drawings.
Related Topics
Concepts
Planar graph
Embedding
Planar
Book embedding
Graph
Combinatorics
Upper and lower bounds
Time complexity
Computer science
Algorithm
Polynomial
Outerplanar graph
Mathematics
Pathwidth
Line graph
Artificial intelligence
Computer graphics (images)
Mathematical analysis
Metadata
- Type
- article
- Language
- en
- Landing Page
- https://doi.org/10.1007/s00453-023-01111-5
- https://link.springer.com/content/pdf/10.1007/s00453-023-01111-5.pdf
- OA Status
- hybrid
- References
- 21
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W4323925505
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W4323925505Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.1007/s00453-023-01111-5Digital Object Identifier
- Title
-
Bitonic st-Orderings for Upward Planar Graphs: Splits and Bends in the Variable Embedding ScenarioWork title
- Type
-
articleOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2023Year of publication
- Publication date
-
2023-03-11Full publication date if available
- Authors
-
Patrizio Angelini, Michael A. Bekos, Henry Förster, Martin GronemannList of authors in order
- Landing page
-
https://doi.org/10.1007/s00453-023-01111-5Publisher landing page
- PDF URL
-
https://link.springer.com/content/pdf/10.1007/s00453-023-01111-5.pdfDirect link to full text PDF
- Open access
-
YesWhether a free full text is available
- OA status
-
hybridOpen access status per OpenAlex
- OA URL
-
https://link.springer.com/content/pdf/10.1007/s00453-023-01111-5.pdfDirect OA link when available
- Concepts
-
Planar graph, Embedding, Planar, Book embedding, Graph, Combinatorics, Upper and lower bounds, Time complexity, Computer science, Algorithm, Polynomial, Outerplanar graph, Mathematics, Pathwidth, Line graph, Artificial intelligence, Computer graphics (images), Mathematical analysisTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
0Total citation count in OpenAlex
- References (count)
-
21Number of works referenced by this work
- Related works (count)
-
10Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W4323925505 |
|---|---|
| doi | https://doi.org/10.1007/s00453-023-01111-5 |
| ids.doi | https://doi.org/10.1007/s00453-023-01111-5 |
| ids.openalex | https://openalex.org/W4323925505 |
| fwci | 0.0 |
| type | article |
| title | Bitonic st-Orderings for Upward Planar Graphs: Splits and Bends in the Variable Embedding Scenario |
| biblio.issue | 9 |
| biblio.volume | 85 |
| biblio.last_page | 2692 |
| biblio.first_page | 2667 |
| topics[0].id | https://openalex.org/T10996 |
| topics[0].field.id | https://openalex.org/fields/17 |
| topics[0].field.display_name | Computer Science |
| topics[0].score | 0.9997000098228455 |
| topics[0].domain.id | https://openalex.org/domains/3 |
| topics[0].domain.display_name | Physical Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/1704 |
| topics[0].subfield.display_name | Computer Graphics and Computer-Aided Design |
| topics[0].display_name | Computational Geometry and Mesh Generation |
| topics[1].id | https://openalex.org/T11522 |
| topics[1].field.id | https://openalex.org/fields/22 |
| topics[1].field.display_name | Engineering |
| topics[1].score | 0.9488000273704529 |
| topics[1].domain.id | https://openalex.org/domains/3 |
| topics[1].domain.display_name | Physical Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/2208 |
| topics[1].subfield.display_name | Electrical and Electronic Engineering |
| topics[1].display_name | VLSI and FPGA Design Techniques |
| funders[0].id | https://openalex.org/F4320321112 |
| funders[0].ror | https://ror.org/03a1kwz48 |
| funders[0].display_name | Eberhard Karls Universität Tübingen |
| is_xpac | False |
| apc_list.value | 2290 |
| apc_list.currency | EUR |
| apc_list.value_usd | 2890 |
| apc_paid.value | 2290 |
| apc_paid.currency | EUR |
| apc_paid.value_usd | 2890 |
| concepts[0].id | https://openalex.org/C101837359 |
| concepts[0].level | 3 |
| concepts[0].score | 0.8085372447967529 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q547823 |
| concepts[0].display_name | Planar graph |
| concepts[1].id | https://openalex.org/C41608201 |
| concepts[1].level | 2 |
| concepts[1].score | 0.7395178079605103 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q980509 |
| concepts[1].display_name | Embedding |
| concepts[2].id | https://openalex.org/C134786449 |
| concepts[2].level | 2 |
| concepts[2].score | 0.6720829010009766 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q3391255 |
| concepts[2].display_name | Planar |
| concepts[3].id | https://openalex.org/C180222743 |
| concepts[3].level | 5 |
| concepts[3].score | 0.6054168343544006 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q4942980 |
| concepts[3].display_name | Book embedding |
| concepts[4].id | https://openalex.org/C132525143 |
| concepts[4].level | 2 |
| concepts[4].score | 0.5142288208007812 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q141488 |
| concepts[4].display_name | Graph |
| concepts[5].id | https://openalex.org/C114614502 |
| concepts[5].level | 1 |
| concepts[5].score | 0.5114347338676453 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q76592 |
| concepts[5].display_name | Combinatorics |
| concepts[6].id | https://openalex.org/C77553402 |
| concepts[6].level | 2 |
| concepts[6].score | 0.4864809215068817 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q13222579 |
| concepts[6].display_name | Upper and lower bounds |
| concepts[7].id | https://openalex.org/C311688 |
| concepts[7].level | 2 |
| concepts[7].score | 0.46028417348861694 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q2393193 |
| concepts[7].display_name | Time complexity |
| concepts[8].id | https://openalex.org/C41008148 |
| concepts[8].level | 0 |
| concepts[8].score | 0.458172082901001 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[8].display_name | Computer science |
| concepts[9].id | https://openalex.org/C11413529 |
| concepts[9].level | 1 |
| concepts[9].score | 0.4559001624584198 |
| concepts[9].wikidata | https://www.wikidata.org/wiki/Q8366 |
| concepts[9].display_name | Algorithm |
| concepts[10].id | https://openalex.org/C90119067 |
| concepts[10].level | 2 |
| concepts[10].score | 0.4269981384277344 |
| concepts[10].wikidata | https://www.wikidata.org/wiki/Q43260 |
| concepts[10].display_name | Polynomial |
| concepts[11].id | https://openalex.org/C125792925 |
| concepts[11].level | 5 |
| concepts[11].score | 0.41254955530166626 |
| concepts[11].wikidata | https://www.wikidata.org/wiki/Q3115604 |
| concepts[11].display_name | Outerplanar graph |
| concepts[12].id | https://openalex.org/C33923547 |
| concepts[12].level | 0 |
| concepts[12].score | 0.3727651834487915 |
| concepts[12].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[12].display_name | Mathematics |
| concepts[13].id | https://openalex.org/C43517604 |
| concepts[13].level | 4 |
| concepts[13].score | 0.198945552110672 |
| concepts[13].wikidata | https://www.wikidata.org/wiki/Q7144893 |
| concepts[13].display_name | Pathwidth |
| concepts[14].id | https://openalex.org/C203776342 |
| concepts[14].level | 3 |
| concepts[14].score | 0.15700176358222961 |
| concepts[14].wikidata | https://www.wikidata.org/wiki/Q1378376 |
| concepts[14].display_name | Line graph |
| concepts[15].id | https://openalex.org/C154945302 |
| concepts[15].level | 1 |
| concepts[15].score | 0.1512787640094757 |
| concepts[15].wikidata | https://www.wikidata.org/wiki/Q11660 |
| concepts[15].display_name | Artificial intelligence |
| concepts[16].id | https://openalex.org/C121684516 |
| concepts[16].level | 1 |
| concepts[16].score | 0.09089380502700806 |
| concepts[16].wikidata | https://www.wikidata.org/wiki/Q7600677 |
| concepts[16].display_name | Computer graphics (images) |
| concepts[17].id | https://openalex.org/C134306372 |
| concepts[17].level | 1 |
| concepts[17].score | 0.07237720489501953 |
| concepts[17].wikidata | https://www.wikidata.org/wiki/Q7754 |
| concepts[17].display_name | Mathematical analysis |
| keywords[0].id | https://openalex.org/keywords/planar-graph |
| keywords[0].score | 0.8085372447967529 |
| keywords[0].display_name | Planar graph |
| keywords[1].id | https://openalex.org/keywords/embedding |
| keywords[1].score | 0.7395178079605103 |
| keywords[1].display_name | Embedding |
| keywords[2].id | https://openalex.org/keywords/planar |
| keywords[2].score | 0.6720829010009766 |
| keywords[2].display_name | Planar |
| keywords[3].id | https://openalex.org/keywords/book-embedding |
| keywords[3].score | 0.6054168343544006 |
| keywords[3].display_name | Book embedding |
| keywords[4].id | https://openalex.org/keywords/graph |
| keywords[4].score | 0.5142288208007812 |
| keywords[4].display_name | Graph |
| keywords[5].id | https://openalex.org/keywords/combinatorics |
| keywords[5].score | 0.5114347338676453 |
| keywords[5].display_name | Combinatorics |
| keywords[6].id | https://openalex.org/keywords/upper-and-lower-bounds |
| keywords[6].score | 0.4864809215068817 |
| keywords[6].display_name | Upper and lower bounds |
| keywords[7].id | https://openalex.org/keywords/time-complexity |
| keywords[7].score | 0.46028417348861694 |
| keywords[7].display_name | Time complexity |
| keywords[8].id | https://openalex.org/keywords/computer-science |
| keywords[8].score | 0.458172082901001 |
| keywords[8].display_name | Computer science |
| keywords[9].id | https://openalex.org/keywords/algorithm |
| keywords[9].score | 0.4559001624584198 |
| keywords[9].display_name | Algorithm |
| keywords[10].id | https://openalex.org/keywords/polynomial |
| keywords[10].score | 0.4269981384277344 |
| keywords[10].display_name | Polynomial |
| keywords[11].id | https://openalex.org/keywords/outerplanar-graph |
| keywords[11].score | 0.41254955530166626 |
| keywords[11].display_name | Outerplanar graph |
| keywords[12].id | https://openalex.org/keywords/mathematics |
| keywords[12].score | 0.3727651834487915 |
| keywords[12].display_name | Mathematics |
| keywords[13].id | https://openalex.org/keywords/pathwidth |
| keywords[13].score | 0.198945552110672 |
| keywords[13].display_name | Pathwidth |
| keywords[14].id | https://openalex.org/keywords/line-graph |
| keywords[14].score | 0.15700176358222961 |
| keywords[14].display_name | Line graph |
| keywords[15].id | https://openalex.org/keywords/artificial-intelligence |
| keywords[15].score | 0.1512787640094757 |
| keywords[15].display_name | Artificial intelligence |
| keywords[16].id | https://openalex.org/keywords/computer-graphics |
| keywords[16].score | 0.09089380502700806 |
| keywords[16].display_name | Computer graphics (images) |
| keywords[17].id | https://openalex.org/keywords/mathematical-analysis |
| keywords[17].score | 0.07237720489501953 |
| keywords[17].display_name | Mathematical analysis |
| language | en |
| locations[0].id | doi:10.1007/s00453-023-01111-5 |
| locations[0].is_oa | True |
| locations[0].source.id | https://openalex.org/S89324355 |
| locations[0].source.issn | 0178-4617, 1432-0541 |
| locations[0].source.type | journal |
| locations[0].source.is_oa | False |
| locations[0].source.issn_l | 0178-4617 |
| locations[0].source.is_core | True |
| locations[0].source.is_in_doaj | False |
| locations[0].source.display_name | Algorithmica |
| locations[0].source.host_organization | https://openalex.org/P4310319900 |
| locations[0].source.host_organization_name | Springer Science+Business Media |
| locations[0].source.host_organization_lineage | https://openalex.org/P4310319900, https://openalex.org/P4310319965 |
| locations[0].source.host_organization_lineage_names | Springer Science+Business Media, Springer Nature |
| locations[0].license | cc-by |
| locations[0].pdf_url | https://link.springer.com/content/pdf/10.1007/s00453-023-01111-5.pdf |
| locations[0].version | publishedVersion |
| locations[0].raw_type | journal-article |
| locations[0].license_id | https://openalex.org/licenses/cc-by |
| locations[0].is_accepted | True |
| locations[0].is_published | True |
| locations[0].raw_source_name | Algorithmica |
| locations[0].landing_page_url | https://doi.org/10.1007/s00453-023-01111-5 |
| indexed_in | crossref |
| authorships[0].author.id | https://openalex.org/A5010111302 |
| authorships[0].author.orcid | https://orcid.org/0000-0002-7602-1524 |
| authorships[0].author.display_name | Patrizio Angelini |
| authorships[0].countries | IT |
| authorships[0].affiliations[0].institution_ids | https://openalex.org/I59857034 |
| authorships[0].affiliations[0].raw_affiliation_string | Department of Mathematics, Natural, and Applied Sciences, John Cabot University, Via della Lungara 233, 00165, Rome, Lazio, Italy |
| authorships[0].institutions[0].id | https://openalex.org/I59857034 |
| authorships[0].institutions[0].ror | https://ror.org/01fjdq469 |
| authorships[0].institutions[0].type | education |
| authorships[0].institutions[0].lineage | https://openalex.org/I59857034 |
| authorships[0].institutions[0].country_code | IT |
| authorships[0].institutions[0].display_name | John Cabot University |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Patrizio Angelini |
| authorships[0].is_corresponding | False |
| authorships[0].raw_affiliation_strings | Department of Mathematics, Natural, and Applied Sciences, John Cabot University, Via della Lungara 233, 00165, Rome, Lazio, Italy |
| authorships[1].author.id | https://openalex.org/A5006472576 |
| authorships[1].author.orcid | https://orcid.org/0000-0002-3414-7444 |
| authorships[1].author.display_name | Michael A. Bekos |
| authorships[1].countries | GR |
| authorships[1].affiliations[0].institution_ids | https://openalex.org/I194019607 |
| authorships[1].affiliations[0].raw_affiliation_string | Department of Mathematics, University of Ioannina, University Campus, 45110, Ioannina, Greece |
| authorships[1].institutions[0].id | https://openalex.org/I194019607 |
| authorships[1].institutions[0].ror | https://ror.org/01qg3j183 |
| authorships[1].institutions[0].type | education |
| authorships[1].institutions[0].lineage | https://openalex.org/I194019607 |
| authorships[1].institutions[0].country_code | GR |
| authorships[1].institutions[0].display_name | University of Ioannina |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | Michael A. Bekos |
| authorships[1].is_corresponding | False |
| authorships[1].raw_affiliation_strings | Department of Mathematics, University of Ioannina, University Campus, 45110, Ioannina, Greece |
| authorships[2].author.id | https://openalex.org/A5035031209 |
| authorships[2].author.orcid | https://orcid.org/0000-0002-1441-4189 |
| authorships[2].author.display_name | Henry Förster |
| authorships[2].countries | DE |
| authorships[2].affiliations[0].institution_ids | https://openalex.org/I8087733 |
| authorships[2].affiliations[0].raw_affiliation_string | Department of Computer Science, University of Tübingen, Sand 13, 72076, Tübingen, Baden-Württemberg, Germany |
| authorships[2].institutions[0].id | https://openalex.org/I8087733 |
| authorships[2].institutions[0].ror | https://ror.org/03a1kwz48 |
| authorships[2].institutions[0].type | education |
| authorships[2].institutions[0].lineage | https://openalex.org/I8087733 |
| authorships[2].institutions[0].country_code | DE |
| authorships[2].institutions[0].display_name | University of Tübingen |
| authorships[2].author_position | middle |
| authorships[2].raw_author_name | Henry Förster |
| authorships[2].is_corresponding | True |
| authorships[2].raw_affiliation_strings | Department of Computer Science, University of Tübingen, Sand 13, 72076, Tübingen, Baden-Württemberg, Germany |
| 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].countries | AT |
| authorships[3].affiliations[0].institution_ids | https://openalex.org/I145847075 |
| authorships[3].affiliations[0].raw_affiliation_string | Algorithms and Complexity Group, TU Wien, Favoritenstraße 9-11, 1040, Vienna, Vienna, Austria |
| authorships[3].institutions[0].id | https://openalex.org/I145847075 |
| authorships[3].institutions[0].ror | https://ror.org/04d836q62 |
| authorships[3].institutions[0].type | education |
| authorships[3].institutions[0].lineage | https://openalex.org/I145847075 |
| authorships[3].institutions[0].country_code | AT |
| authorships[3].institutions[0].display_name | TU Wien |
| authorships[3].author_position | last |
| authorships[3].raw_author_name | Martin Gronemann |
| authorships[3].is_corresponding | False |
| authorships[3].raw_affiliation_strings | Algorithms and Complexity Group, TU Wien, Favoritenstraße 9-11, 1040, Vienna, Vienna, Austria |
| has_content.pdf | True |
| has_content.grobid_xml | True |
| is_paratext | False |
| open_access.is_oa | True |
| open_access.oa_url | https://link.springer.com/content/pdf/10.1007/s00453-023-01111-5.pdf |
| open_access.oa_status | hybrid |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-10-10T00:00:00 |
| display_name | Bitonic st-Orderings for Upward Planar Graphs: Splits and Bends in the Variable Embedding Scenario |
| has_fulltext | True |
| is_retracted | False |
| updated_date | 2025-11-06T03:46:38.306776 |
| primary_topic.id | https://openalex.org/T10996 |
| primary_topic.field.id | https://openalex.org/fields/17 |
| primary_topic.field.display_name | Computer Science |
| primary_topic.score | 0.9997000098228455 |
| primary_topic.domain.id | https://openalex.org/domains/3 |
| primary_topic.domain.display_name | Physical Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/1704 |
| primary_topic.subfield.display_name | Computer Graphics and Computer-Aided Design |
| primary_topic.display_name | Computational Geometry and Mesh Generation |
| related_works | https://openalex.org/W3216500139, https://openalex.org/W3034858646, https://openalex.org/W1759199114, https://openalex.org/W4287758186, https://openalex.org/W1491152805, https://openalex.org/W2048639803, https://openalex.org/W3135899633, https://openalex.org/W2995965358, https://openalex.org/W3002061974, https://openalex.org/W2009558719 |
| cited_by_count | 0 |
| locations_count | 1 |
| best_oa_location.id | doi:10.1007/s00453-023-01111-5 |
| best_oa_location.is_oa | True |
| best_oa_location.source.id | https://openalex.org/S89324355 |
| best_oa_location.source.issn | 0178-4617, 1432-0541 |
| best_oa_location.source.type | journal |
| best_oa_location.source.is_oa | False |
| best_oa_location.source.issn_l | 0178-4617 |
| best_oa_location.source.is_core | True |
| best_oa_location.source.is_in_doaj | False |
| best_oa_location.source.display_name | Algorithmica |
| best_oa_location.source.host_organization | https://openalex.org/P4310319900 |
| best_oa_location.source.host_organization_name | Springer Science+Business Media |
| best_oa_location.source.host_organization_lineage | https://openalex.org/P4310319900, https://openalex.org/P4310319965 |
| best_oa_location.source.host_organization_lineage_names | Springer Science+Business Media, Springer Nature |
| best_oa_location.license | cc-by |
| best_oa_location.pdf_url | https://link.springer.com/content/pdf/10.1007/s00453-023-01111-5.pdf |
| best_oa_location.version | publishedVersion |
| best_oa_location.raw_type | journal-article |
| best_oa_location.license_id | https://openalex.org/licenses/cc-by |
| best_oa_location.is_accepted | True |
| best_oa_location.is_published | True |
| best_oa_location.raw_source_name | Algorithmica |
| best_oa_location.landing_page_url | https://doi.org/10.1007/s00453-023-01111-5 |
| primary_location.id | doi:10.1007/s00453-023-01111-5 |
| primary_location.is_oa | True |
| primary_location.source.id | https://openalex.org/S89324355 |
| primary_location.source.issn | 0178-4617, 1432-0541 |
| primary_location.source.type | journal |
| primary_location.source.is_oa | False |
| primary_location.source.issn_l | 0178-4617 |
| primary_location.source.is_core | True |
| primary_location.source.is_in_doaj | False |
| primary_location.source.display_name | Algorithmica |
| primary_location.source.host_organization | https://openalex.org/P4310319900 |
| primary_location.source.host_organization_name | Springer Science+Business Media |
| primary_location.source.host_organization_lineage | https://openalex.org/P4310319900, https://openalex.org/P4310319965 |
| primary_location.source.host_organization_lineage_names | Springer Science+Business Media, Springer Nature |
| primary_location.license | cc-by |
| primary_location.pdf_url | https://link.springer.com/content/pdf/10.1007/s00453-023-01111-5.pdf |
| primary_location.version | publishedVersion |
| primary_location.raw_type | journal-article |
| primary_location.license_id | https://openalex.org/licenses/cc-by |
| primary_location.is_accepted | True |
| primary_location.is_published | True |
| primary_location.raw_source_name | Algorithmica |
| primary_location.landing_page_url | https://doi.org/10.1007/s00453-023-01111-5 |
| publication_date | 2023-03-11 |
| publication_year | 2023 |
| referenced_works | https://openalex.org/W2003525146, https://openalex.org/W2045870980, https://openalex.org/W1984308317, https://openalex.org/W2117205241, https://openalex.org/W2082205964, https://openalex.org/W2091252880, https://openalex.org/W104000684, https://openalex.org/W2963534320, https://openalex.org/W2596061115, https://openalex.org/W2517713975, https://openalex.org/W2055127468, https://openalex.org/W2962932970, https://openalex.org/W2039512408, https://openalex.org/W2024366499, https://openalex.org/W1534309112, https://openalex.org/W2097248064, https://openalex.org/W1971813586, https://openalex.org/W2114785943, https://openalex.org/W4213350132, https://openalex.org/W4250733435, https://openalex.org/W2002906478 |
| referenced_works_count | 21 |
| abstract_inverted_index.. | 170 |
| abstract_inverted_index.a | 11, 60, 85, 103, 128, 177 |
| abstract_inverted_index.n | 158 |
| abstract_inverted_index.In | 197 |
| abstract_inverted_index.We | 119, 227, 259 |
| abstract_inverted_index.an | 52, 76, 153, 238 |
| abstract_inverted_index.as | 10, 84, 93, 96 |
| abstract_inverted_index.at | 42, 244 |
| abstract_inverted_index.be | 234 |
| abstract_inverted_index.by | 126, 190, 236, 289 |
| abstract_inverted_index.in | 48, 91, 106, 114, 123, 204, 256, 276, 281, 297 |
| abstract_inverted_index.is | 82, 88, 160, 173 |
| abstract_inverted_index.it | 111, 172 |
| abstract_inverted_index.no | 225 |
| abstract_inverted_index.of | 34, 136, 149, 152, 194, 199, 295 |
| abstract_inverted_index.on | 31, 146, 292 |
| abstract_inverted_index.st | 2, 5, 53, 62, 139, 154, 179, 186, 239 |
| abstract_inverted_index.to | 13, 25, 175 |
| abstract_inverted_index.we | 269 |
| abstract_inverted_index.For | 51 |
| abstract_inverted_index.The | 142 |
| abstract_inverted_index.all | 134, 195 |
| abstract_inverted_index.and | 279 |
| abstract_inverted_index.any | 182 |
| abstract_inverted_index.few | 94 |
| abstract_inverted_index.for | 4, 36, 71, 184, 263 |
| abstract_inverted_index.gap | 122 |
| abstract_inverted_index.may | 65 |
| abstract_inverted_index.not | 58 |
| abstract_inverted_index.one | 44, 64, 87 |
| abstract_inverted_index.per | 46 |
| abstract_inverted_index.the | 27, 32, 72, 107, 115, 124, 137, 147, 185, 192, 207, 222, 272, 293 |
| abstract_inverted_index.been | 23 |
| abstract_inverted_index.bend | 45 |
| abstract_inverted_index.both | 257 |
| abstract_inverted_index.cope | 14 |
| abstract_inverted_index.does | 57 |
| abstract_inverted_index.each | 80 |
| abstract_inverted_index.edge | 47 |
| abstract_inverted_index.have | 22 |
| abstract_inverted_index.idea | 231 |
| abstract_inverted_index.into | 210, 224 |
| abstract_inverted_index.most | 43 |
| abstract_inverted_index.open | 113 |
| abstract_inverted_index.over | 133 |
| abstract_inverted_index.show | 228 |
| abstract_inverted_index.such | 69, 75, 298 |
| abstract_inverted_index.that | 56, 70, 131, 229, 242 |
| abstract_inverted_index.they | 21 |
| abstract_inverted_index.this | 99, 121, 230 |
| abstract_inverted_index.used | 24 |
| abstract_inverted_index.were | 8 |
| abstract_inverted_index.with | 15, 41, 157, 265, 286 |
| abstract_inverted_index.Since | 79 |
| abstract_inverted_index.While | 98 |
| abstract_inverted_index.admit | 59 |
| abstract_inverted_index.area, | 206, 288 |
| abstract_inverted_index.area. | 50 |
| abstract_inverted_index.bend, | 86 |
| abstract_inverted_index.bends | 35, 280, 296 |
| abstract_inverted_index.bound | 30, 145 |
| abstract_inverted_index.close | 120 |
| abstract_inverted_index.edges | 68, 95 |
| abstract_inverted_index.fixed | 108 |
| abstract_inverted_index.graph | 17, 55, 74, 156, 188, 241 |
| abstract_inverted_index.input | 138 |
| abstract_inverted_index.least | 245 |
| abstract_inverted_index.lower | 144 |
| abstract_inverted_index.needs | 243 |
| abstract_inverted_index.small | 266 |
| abstract_inverted_index.split | 66, 81, 183 |
| abstract_inverted_index.terms | 198 |
| abstract_inverted_index.upper | 29 |
| abstract_inverted_index.while | 221 |
| abstract_inverted_index.admits | 102 |
| abstract_inverted_index.always | 233 |
| abstract_inverted_index.bends, | 220 |
| abstract_inverted_index.bends. | 226 |
| abstract_inverted_index.bounds | 262, 291 |
| abstract_inverted_index.cannot | 232 |
| abstract_inverted_index.edges. | 196 |
| abstract_inverted_index.former | 208 |
| abstract_inverted_index.graph. | 141 |
| abstract_inverted_index.graphs | 7, 264 |
| abstract_inverted_index.latter | 223 |
| abstract_inverted_index.method | 12 |
| abstract_inverted_index.number | 33, 148, 294 |
| abstract_inverted_index.obtain | 26 |
| abstract_inverted_index.planar | 38, 201, 283 |
| abstract_inverted_index.splits | 151, 255, 275 |
| abstract_inverted_index.upward | 37, 200, 282 |
| abstract_inverted_index.$$n-3$$ | 161, 211 |
| abstract_inverted_index.$$n-5$$ | 246 |
| abstract_inverted_index.-planar | 6, 54, 140, 155, 187, 240 |
| abstract_inverted_index.Bitonic | 1 |
| abstract_inverted_index.between | 274 |
| abstract_inverted_index.bitonic | 61, 178, 277 |
| abstract_inverted_index.certain | 67 |
| abstract_inverted_index.compute | 176 |
| abstract_inverted_index.degree. | 267 |
| abstract_inverted_index.drawing | 18 |
| abstract_inverted_index.exists. | 78 |
| abstract_inverted_index.further | 270 |
| abstract_inverted_index.problem | 101 |
| abstract_inverted_index.provide | 260 |
| abstract_inverted_index.remains | 112 |
| abstract_inverted_index.several | 16 |
| abstract_inverted_index.usually | 89 |
| abstract_inverted_index.without | 181 |
| abstract_inverted_index.Abstract | 0 |
| abstract_inverted_index.Finally, | 268 |
| abstract_inverted_index.However, | 171 |
| abstract_inverted_index.Notably, | 20 |
| abstract_inverted_index.drawings | 40, 203, 285 |
| abstract_inverted_index.obtained | 189 |
| abstract_inverted_index.ordering | 77 |
| abstract_inverted_index.polyline | 39, 202, 284 |
| abstract_inverted_index.possible | 174 |
| abstract_inverted_index.required | 150 |
| abstract_inverted_index.setting, | 110 |
| abstract_inverted_index.setting. | 118 |
| abstract_inverted_index.variable | 116 |
| abstract_inverted_index.vertices | 159 |
| abstract_inverted_index.-ordering | 180 |
| abstract_inverted_index.<mml:math | 162, 212, 247 |
| abstract_inverted_index.algorithm | 105, 130 |
| abstract_inverted_index.analogous | 261 |
| abstract_inverted_index.drawings. | 299 |
| abstract_inverted_index.embedding | 109, 117 |
| abstract_inverted_index.exploited | 235 |
| abstract_inverted_index.optimizes | 132 |
| abstract_inverted_index.possible. | 97 |
| abstract_inverted_index.problems. | 19 |
| abstract_inverted_index.providing | 127, 290 |
| abstract_inverted_index.resulting | 73 |
| abstract_inverted_index.reversing | 191 |
| abstract_inverted_index.splitting | 92 |
| abstract_inverted_index.-ordering, | 63 |
| abstract_inverted_index.-orderings | 3 |
| abstract_inverted_index.<mml:mrow> | 164, 214, 249 |
| abstract_inverted_index.best-known | 28, 143 |
| abstract_inverted_index.describing | 237 |
| abstract_inverted_index.embeddings | 135 |
| abstract_inverted_index.interested | 90 |
| abstract_inverted_index.introduced | 9 |
| abstract_inverted_index.literature | 125 |
| abstract_inverted_index.polynomial | 49, 205, 287 |
| abstract_inverted_index.translates | 209 |
| abstract_inverted_index.</mml:math> | 169, 219, 254 |
| abstract_inverted_index.</mml:mrow> | 168, 218, 253 |
| abstract_inverted_index.interpreted | 83 |
| abstract_inverted_index.investigate | 271 |
| abstract_inverted_index.linear-time | 104, 129 |
| abstract_inverted_index.orientation | 193 |
| abstract_inverted_index.optimization | 100 |
| abstract_inverted_index.relationship | 273 |
| abstract_inverted_index.st-orderings | 278 |
| abstract_inverted_index.orientations. | 258 |
| abstract_inverted_index.<mml:mi>n</mml:mi> | 165, 215, 250 |
| abstract_inverted_index.<mml:mn>3</mml:mn> | 167, 217 |
| abstract_inverted_index.<mml:mn>5</mml:mn> | 252 |
| abstract_inverted_index.<mml:mo>-</mml:mo> | 166, 216, 251 |
| abstract_inverted_index.xmlns:mml="http://www.w3.org/1998/Math/MathML"> | 163, 213, 248 |
| cited_by_percentile_year | |
| corresponding_author_ids | https://openalex.org/A5035031209 |
| countries_distinct_count | 4 |
| institutions_distinct_count | 4 |
| corresponding_institution_ids | https://openalex.org/I8087733 |
| citation_normalized_percentile.value | 0.04161585 |
| citation_normalized_percentile.is_in_top_1_percent | False |
| citation_normalized_percentile.is_in_top_10_percent | False |