{"ID":2877669,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.19913","arxiv_id":"2508.19913","title":"Internally-Convex Drawings of Outerplanar Graphs in Small Area","abstract":"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.","short_abstract":"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 out...","url_abs":"https://arxiv.org/abs/2508.19913","url_pdf":"https://arxiv.org/pdf/2508.19913v1","authors":"[\"Michael A. Bekos\",\"Giordano Da Lozzo\",\"Fabrizio Frati\",\"Giuseppe Liotta\",\"Antonios Symvonis\"]","published":"2025-08-27T14:19:24Z","proceeding":"cs.CG","tasks":"[\"cs.CG\",\"cs.DM\",\"cs.DS\"]","methods":"[]","has_code":false}