2025/08/27 by Michael A. Bekos, Bekos, Michael A., Giordano Da Lozzo +7
#cs.CG #cs.DM #cs.DS
paper · pdf · doi:10.48550/arxiv.2508.19913
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(n2) area. In this paper, we present an algorithm to compute such drawings in O(n1.5) area. We also consider outerplanar drawings in which the internal faces are required to be strictly-convex polygons. In this setting, we provide a Θ(nk2) area bound for n-vertex outerplanar graphs whose weak dual is a path and whose maximum face size is k and a Θ(nd2) area bound for n-vertex outerplanar graphs whose diameter is bounded by d.