ContactPerson: agarg@cse.buffalo.edu Remote host: ubppp249-8.dialin.buffalo.edu ### Begin Citation ### Do not delete this line ### %R 2003-11 %U /tmp/outerplanar.pdf %A Garg, Ashim %A Rusu, Adrian %T Area-Efficient Drawings of Outerplanar Graphs %D September 18, 2003 %I Department of Computer Science and Engineering, SUNY Buffalo %K graph, outerplanar, area, planar, straight-line %X It is well-known that a planar graph with $n$ nodes admits a planar straight-line grid drawing with $O(n^2)$ area, and in the worst case it requires $\Omega(n^2)$ area. It is also known that a binary tree with $n$ nodes admits a planar straight-line grid drawing with $O(n)$ area. Thus, there is wide gap between the $\Theta(n^2)$ area-requirement of general planar graphs and the $\Theta(n)$ area-requirement of binary trees. It is therefore important to investigate special categories of planar graphs to determine if they can be drawn in $o(n^2)$ area. Outerplanar graphs form an important category of planar graphs. We investigate the area-requirement of planar straight-line grid drawings of outerplanar graphs. Currently the best known bound on the area-requirement of such a drawing of an outerplanar graph with $n$ vertices is $O(n^2)$, which is that same as for general planar graphs. Hence, a fundamental question arises that can be draw an outerplanar graph in this fashion in $o(n^2)$ area? In this paper, we provide a partial answer to this question by proving that an outerplanar graph with $n$ vertices and degree $d$ can be drawn in this fashion in area $O(dn^{1.48})$ in $O(n\log n)$ time. This implies that an outerplanar graph with $n$ vertices and degree $d$, where $d= o(n^{0.52})$, can be drawn in this fashion in $o(n^2)$ area. From a broader perspective, our contribution is in showing a sufficiently large natural category of planar graphs that can be drawn in $o(n^2)$ area.