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 provide a $\Theta (n{k}^2)$ area bound for $n$-vertex outerplanar graphs whose weak dual is a path and whose maximum face size is $k$ and a $\Theta (n{d}^2)$ area bound for $n$-vertex outerplanar graphs whose diameter is bounded by $d$.

Extended version of the paper "Internally-Convex Drawings of Outerplanar Graphs in Small Area" accepted for presentation at the "33rd International Symposium on Graph Drawing and Network Visualization" (GD 2025)