Internally-Convex Drawings of Outerplanar Graphs in Small Area

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 $\mathrm{\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 $\mathrm{\Theta }(n{d}^2)$ area bound for $n$-vertex outerplanar graphs whose diameter is bounded by $d$.