Area-efficient planar straight-line drawings of outerplanar graphs

It is important to minimize the area of a drawing of a graph, so that the drawing can fit in a small drawing-space. It is well-known that a planar graph with nn vertices admits a planar straight-line grid drawing with O(n2)O(n2) area [H. de Fraysseix, J. Pach, R. Pollack, How to draw a planar graph on a grid, Combinatorica 10(1) (1990) 41–51; W. Schnyder, Embedding planar graphs on the grid, in: Proceedings of the First ACM-SIAM Symposium on Discrete Algorithms, 1990, pp. 138–148]. Unfortunately, there is a matching lower-bound of Ω(n2)Ω(n2) on the area-requirements of the planar straight-line grid drawings of certain planar graphs. Hence, it is important to investigate important categories of planar graphs to determine if they admit planar straight-line grid drawings with o(n2)o(n2) area.In this paper, we investigate an important category of planar graphs, namely, outerplanar graphs. We show that an outerplanar graph GG with degree dd admits a planar straight-line grid drawing with area O(dn1.48)O(dn1.48) in O(n)O(n) time. This implies that if d=o(n0.52)d=o(n0.52), then GG can be drawn in this manner in o(n2)o(n2) area.