Internally-Convex Drawings of Outerplanar Graphs in Small Area
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914009156943872 |
|---|---|
| author | Bekos, Michael A. Da Lozzo, Giordano Frati, Fabrizio Liotta, Giuseppe Symvonis, Antonios |
| author_facet | Bekos, Michael A. Da Lozzo, Giordano Frati, Fabrizio Liotta, Giuseppe Symvonis, Antonios |
| contents | A well-known result by Kant [Algorithmica, 1996] implies that n-vertex outerplane graphs admit embedding-preserving planar straight-line grid drawings where the internal faces are convex polygons in $O(n^2)$ area. In this paper, we present an algorithm to compute such drawings in $O(n^{1.5})$ area. We also consider outerplanar drawings in which the internal faces are required to be strictly-convex polygons. In this setting, we consider outerplanar graphs whose weak dual is a path and give a drawing algorithm that achieves $Θ(nk^2)$ area, where $k$ is the maximum size of an internal facial cycle. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_19913 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Internally-Convex Drawings of Outerplanar Graphs in Small Area Bekos, Michael A. Da Lozzo, Giordano Frati, Fabrizio Liotta, Giuseppe Symvonis, Antonios Computational Geometry Discrete Mathematics Data Structures and Algorithms A well-known result by Kant [Algorithmica, 1996] implies that n-vertex outerplane graphs admit embedding-preserving planar straight-line grid drawings where the internal faces are convex polygons in $O(n^2)$ area. In this paper, we present an algorithm to compute such drawings in $O(n^{1.5})$ area. We also consider outerplanar drawings in which the internal faces are required to be strictly-convex polygons. In this setting, we consider outerplanar graphs whose weak dual is a path and give a drawing algorithm that achieves $Θ(nk^2)$ area, where $k$ is the maximum size of an internal facial cycle. |
| title | Internally-Convex Drawings of Outerplanar Graphs in Small Area |
| topic | Computational Geometry Discrete Mathematics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2508.19913 |