2026-07-24T06:34:41Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25004 2026-02-09T07:52:45Z ddc:004 open_access

Internally-Convex Drawings of Outerplanar Graphs in Small Area Bekos, Michael A. Da Lozzo, Giordano Frati, Fabrizio Liotta, Giuseppe Symvonis, Antonios Grid drawings convexity area bounds outerplanar graphs 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²) area. In this paper, we present an algorithm to compute such drawings in O(n¹·⁵) 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²) area, where k is the maximum size of an internal facial cycle. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Michael A. Bekos and Giordano Da Lozzo and Fabrizio Frati and Giuseppe Liotta and Antonios Symvonis 2025 Is Part Of LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.GD.2025.18 urn:nbn:de:0030-drops-250042 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.18 eng https://creativecommons.org/licenses/by/4.0/legalcode