Convex Grid Drawings of Planar Graphs with Constant Edge-Vertex Resolution Article Swipe
Michael A. Bekos
,
Martin Gronemann
,
Fabrizio Montecchiani
,
Antonios Symvonis
·
YOU?
·
· 2022
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2204.14040
YOU?
·
· 2022
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2204.14040
We continue the study of the area requirement of convex straight-line grid drawings of 3-connected plane graphs, which has been intensively investigated in the last decades. Motivated by applications, such as graph editors, we additionally require the obtained drawings to have bounded edge-vertex resolution, that is, the closest distance between a vertex and any non-incident edge is lower bounded by a constant that does not depend on the size of the graph. We present a drawing algorithm that takes as input a 3-connected plane graph with n vertices and f internal faces and computes a convex straight-line drawing with edge-vertex resolution at least 1/2 on an integer grid of size (n-2+a)x(n-2+a), where a=min{n-3,f}. Our result improves the previously best-known area bound of (3n-7)x(3n-7)/2 by Chrobak, Goodrich and Tamassia.
Related Topics
Concepts
Metadata
- Type
- preprint
- Language
- en
- Landing Page
- http://arxiv.org/abs/2204.14040
- https://arxiv.org/pdf/2204.14040
- OA Status
- green
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W4225329095
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W4225329095Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.48550/arxiv.2204.14040Digital Object Identifier
- Title
-
Convex Grid Drawings of Planar Graphs with Constant Edge-Vertex ResolutionWork title
- Type
-
preprintOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2022Year of publication
- Publication date
-
2022-04-29Full publication date if available
- Authors
-
Michael A. Bekos, Martin Gronemann, Fabrizio Montecchiani, Antonios SymvonisList of authors in order
- Landing page
-
https://arxiv.org/abs/2204.14040Publisher landing page
- PDF URL
-
https://arxiv.org/pdf/2204.14040Direct 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/2204.14040Direct OA link when available
- Concepts
-
Combinatorics, Planar graph, Vertex (graph theory), Mathematics, Regular polygon, Bounded function, Grid, Graph, Discrete mathematics, Geometry, Mathematical analysisTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
0Total citation count in OpenAlex
- Related works (count)
-
10Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W4225329095 |
|---|---|
| doi | https://doi.org/10.48550/arxiv.2204.14040 |
| ids.doi | https://doi.org/10.48550/arxiv.2204.14040 |
| ids.openalex | https://openalex.org/W4225329095 |
| fwci | |
| type | preprint |
| title | Convex Grid Drawings of Planar Graphs with Constant Edge-Vertex Resolution |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | |
| 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.9994000196456909 |
| 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/T12292 |
| topics[1].field.id | https://openalex.org/fields/17 |
| topics[1].field.display_name | Computer Science |
| topics[1].score | 0.9751999974250793 |
| topics[1].domain.id | https://openalex.org/domains/3 |
| topics[1].domain.display_name | Physical Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/1707 |
| topics[1].subfield.display_name | Computer Vision and Pattern Recognition |
| topics[1].display_name | Graph Theory and Algorithms |
| topics[2].id | https://openalex.org/T11164 |
| topics[2].field.id | https://openalex.org/fields/23 |
| topics[2].field.display_name | Environmental Science |
| topics[2].score | 0.9524999856948853 |
| topics[2].domain.id | https://openalex.org/domains/3 |
| topics[2].domain.display_name | Physical Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/2305 |
| topics[2].subfield.display_name | Environmental Engineering |
| topics[2].display_name | Remote Sensing and LiDAR Applications |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C114614502 |
| concepts[0].level | 1 |
| concepts[0].score | 0.7757267951965332 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q76592 |
| concepts[0].display_name | Combinatorics |
| concepts[1].id | https://openalex.org/C101837359 |
| concepts[1].level | 3 |
| concepts[1].score | 0.6697287559509277 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q547823 |
| concepts[1].display_name | Planar graph |
| concepts[2].id | https://openalex.org/C80899671 |
| concepts[2].level | 3 |
| concepts[2].score | 0.6442928314208984 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q1304193 |
| concepts[2].display_name | Vertex (graph theory) |
| concepts[3].id | https://openalex.org/C33923547 |
| concepts[3].level | 0 |
| concepts[3].score | 0.5720077753067017 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[3].display_name | Mathematics |
| concepts[4].id | https://openalex.org/C112680207 |
| concepts[4].level | 2 |
| concepts[4].score | 0.5622692108154297 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q714886 |
| concepts[4].display_name | Regular polygon |
| concepts[5].id | https://openalex.org/C34388435 |
| concepts[5].level | 2 |
| concepts[5].score | 0.47046124935150146 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q2267362 |
| concepts[5].display_name | Bounded function |
| concepts[6].id | https://openalex.org/C187691185 |
| concepts[6].level | 2 |
| concepts[6].score | 0.4642065167427063 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q2020720 |
| concepts[6].display_name | Grid |
| concepts[7].id | https://openalex.org/C132525143 |
| concepts[7].level | 2 |
| concepts[7].score | 0.39456403255462646 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q141488 |
| concepts[7].display_name | Graph |
| concepts[8].id | https://openalex.org/C118615104 |
| concepts[8].level | 1 |
| concepts[8].score | 0.3227542042732239 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q121416 |
| concepts[8].display_name | Discrete mathematics |
| concepts[9].id | https://openalex.org/C2524010 |
| concepts[9].level | 1 |
| concepts[9].score | 0.28523215651512146 |
| concepts[9].wikidata | https://www.wikidata.org/wiki/Q8087 |
| concepts[9].display_name | Geometry |
| concepts[10].id | https://openalex.org/C134306372 |
| concepts[10].level | 1 |
| concepts[10].score | 0.058368563652038574 |
| concepts[10].wikidata | https://www.wikidata.org/wiki/Q7754 |
| concepts[10].display_name | Mathematical analysis |
| keywords[0].id | https://openalex.org/keywords/combinatorics |
| keywords[0].score | 0.7757267951965332 |
| keywords[0].display_name | Combinatorics |
| keywords[1].id | https://openalex.org/keywords/planar-graph |
| keywords[1].score | 0.6697287559509277 |
| keywords[1].display_name | Planar graph |
| keywords[2].id | https://openalex.org/keywords/vertex |
| keywords[2].score | 0.6442928314208984 |
| keywords[2].display_name | Vertex (graph theory) |
| keywords[3].id | https://openalex.org/keywords/mathematics |
| keywords[3].score | 0.5720077753067017 |
| keywords[3].display_name | Mathematics |
| keywords[4].id | https://openalex.org/keywords/regular-polygon |
| keywords[4].score | 0.5622692108154297 |
| keywords[4].display_name | Regular polygon |
| keywords[5].id | https://openalex.org/keywords/bounded-function |
| keywords[5].score | 0.47046124935150146 |
| keywords[5].display_name | Bounded function |
| keywords[6].id | https://openalex.org/keywords/grid |
| keywords[6].score | 0.4642065167427063 |
| keywords[6].display_name | Grid |
| keywords[7].id | https://openalex.org/keywords/graph |
| keywords[7].score | 0.39456403255462646 |
| keywords[7].display_name | Graph |
| keywords[8].id | https://openalex.org/keywords/discrete-mathematics |
| keywords[8].score | 0.3227542042732239 |
| keywords[8].display_name | Discrete mathematics |
| keywords[9].id | https://openalex.org/keywords/geometry |
| keywords[9].score | 0.28523215651512146 |
| keywords[9].display_name | Geometry |
| keywords[10].id | https://openalex.org/keywords/mathematical-analysis |
| keywords[10].score | 0.058368563652038574 |
| keywords[10].display_name | Mathematical analysis |
| language | en |
| locations[0].id | pmh:oai:arXiv.org:2204.14040 |
| 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/2204.14040 |
| 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/2204.14040 |
| locations[1].id | doi:10.48550/arxiv.2204.14040 |
| 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 | public-domain |
| locations[1].pdf_url | |
| locations[1].version | |
| locations[1].raw_type | article |
| locations[1].license_id | https://openalex.org/licenses/public-domain |
| 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.2204.14040 |
| 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/A5080178526 |
| authorships[1].author.orcid | https://orcid.org/0000-0003-2565-090X |
| authorships[1].author.display_name | Martin Gronemann |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | Gronemann, Martin |
| authorships[1].is_corresponding | False |
| authorships[2].author.id | https://openalex.org/A5006763389 |
| authorships[2].author.orcid | https://orcid.org/0000-0002-0543-8912 |
| authorships[2].author.display_name | Fabrizio Montecchiani |
| authorships[2].author_position | middle |
| authorships[2].raw_author_name | Montecchiani, Fabrizio |
| authorships[2].is_corresponding | False |
| authorships[3].author.id | https://openalex.org/A5011976306 |
| authorships[3].author.orcid | https://orcid.org/0000-0002-0280-741X |
| authorships[3].author.display_name | Antonios Symvonis |
| authorships[3].author_position | last |
| authorships[3].raw_author_name | Symvonis, Antonios |
| authorships[3].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/2204.14040 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-10-10T00:00:00 |
| display_name | Convex Grid Drawings of Planar Graphs with Constant Edge-Vertex Resolution |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-06T06:51:31.235846 |
| 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.9994000196456909 |
| 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/W3013085049, https://openalex.org/W1560496689, https://openalex.org/W1992739770, https://openalex.org/W4386900933, https://openalex.org/W4229058035, https://openalex.org/W3125672081, https://openalex.org/W4385301946, https://openalex.org/W2006389905, https://openalex.org/W2296389180, https://openalex.org/W2073023540 |
| cited_by_count | 0 |
| locations_count | 2 |
| best_oa_location.id | pmh:oai:arXiv.org:2204.14040 |
| 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/2204.14040 |
| 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/2204.14040 |
| primary_location.id | pmh:oai:arXiv.org:2204.14040 |
| 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/2204.14040 |
| 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/2204.14040 |
| publication_date | 2022-04-29 |
| publication_year | 2022 |
| referenced_works_count | 0 |
| abstract_inverted_index.a | 50, 60, 74, 81, 94 |
| abstract_inverted_index.f | 89 |
| abstract_inverted_index.n | 86 |
| abstract_inverted_index.We | 0, 72 |
| abstract_inverted_index.an | 105 |
| abstract_inverted_index.as | 30, 79 |
| abstract_inverted_index.at | 101 |
| abstract_inverted_index.by | 27, 59, 123 |
| abstract_inverted_index.in | 22 |
| abstract_inverted_index.is | 56 |
| abstract_inverted_index.of | 4, 8, 13, 69, 108, 121 |
| abstract_inverted_index.on | 66, 104 |
| abstract_inverted_index.to | 39 |
| abstract_inverted_index.we | 33 |
| abstract_inverted_index.1/2 | 103 |
| abstract_inverted_index.Our | 113 |
| abstract_inverted_index.and | 52, 88, 92, 126 |
| abstract_inverted_index.any | 53 |
| abstract_inverted_index.has | 18 |
| abstract_inverted_index.is, | 45 |
| abstract_inverted_index.not | 64 |
| abstract_inverted_index.the | 2, 5, 23, 36, 46, 67, 70, 116 |
| abstract_inverted_index.area | 6, 119 |
| abstract_inverted_index.been | 19 |
| abstract_inverted_index.does | 63 |
| abstract_inverted_index.edge | 55 |
| abstract_inverted_index.grid | 11, 107 |
| abstract_inverted_index.have | 40 |
| abstract_inverted_index.last | 24 |
| abstract_inverted_index.size | 68, 109 |
| abstract_inverted_index.such | 29 |
| abstract_inverted_index.that | 44, 62, 77 |
| abstract_inverted_index.with | 85, 98 |
| abstract_inverted_index.bound | 120 |
| abstract_inverted_index.faces | 91 |
| abstract_inverted_index.graph | 31, 84 |
| abstract_inverted_index.input | 80 |
| abstract_inverted_index.least | 102 |
| abstract_inverted_index.lower | 57 |
| abstract_inverted_index.plane | 15, 83 |
| abstract_inverted_index.study | 3 |
| abstract_inverted_index.takes | 78 |
| abstract_inverted_index.where | 111 |
| abstract_inverted_index.which | 17 |
| abstract_inverted_index.convex | 9, 95 |
| abstract_inverted_index.depend | 65 |
| abstract_inverted_index.graph. | 71 |
| abstract_inverted_index.result | 114 |
| abstract_inverted_index.vertex | 51 |
| abstract_inverted_index.between | 49 |
| abstract_inverted_index.bounded | 41, 58 |
| abstract_inverted_index.closest | 47 |
| abstract_inverted_index.drawing | 75, 97 |
| abstract_inverted_index.graphs, | 16 |
| abstract_inverted_index.integer | 106 |
| abstract_inverted_index.present | 73 |
| abstract_inverted_index.require | 35 |
| abstract_inverted_index.Chrobak, | 124 |
| abstract_inverted_index.Goodrich | 125 |
| abstract_inverted_index.computes | 93 |
| abstract_inverted_index.constant | 61 |
| abstract_inverted_index.continue | 1 |
| abstract_inverted_index.decades. | 25 |
| abstract_inverted_index.distance | 48 |
| abstract_inverted_index.drawings | 12, 38 |
| abstract_inverted_index.editors, | 32 |
| abstract_inverted_index.improves | 115 |
| abstract_inverted_index.internal | 90 |
| abstract_inverted_index.obtained | 37 |
| abstract_inverted_index.vertices | 87 |
| abstract_inverted_index.Motivated | 26 |
| abstract_inverted_index.Tamassia. | 127 |
| abstract_inverted_index.algorithm | 76 |
| abstract_inverted_index.best-known | 118 |
| abstract_inverted_index.previously | 117 |
| abstract_inverted_index.resolution | 100 |
| abstract_inverted_index.3-connected | 14, 82 |
| abstract_inverted_index.edge-vertex | 42, 99 |
| abstract_inverted_index.intensively | 20 |
| abstract_inverted_index.requirement | 7 |
| abstract_inverted_index.resolution, | 43 |
| abstract_inverted_index.additionally | 34 |
| abstract_inverted_index.investigated | 21 |
| abstract_inverted_index.non-incident | 54 |
| abstract_inverted_index.a=min{n-3,f}. | 112 |
| abstract_inverted_index.applications, | 28 |
| abstract_inverted_index.straight-line | 10, 96 |
| abstract_inverted_index.(3n-7)x(3n-7)/2 | 122 |
| abstract_inverted_index.(n-2+a)x(n-2+a), | 110 |
| cited_by_percentile_year | |
| countries_distinct_count | 0 |
| institutions_distinct_count | 4 |
| sustainable_development_goals[0].id | https://metadata.un.org/sdg/11 |
| sustainable_development_goals[0].score | 0.4699999988079071 |
| sustainable_development_goals[0].display_name | Sustainable cities and communities |
| citation_normalized_percentile |