LR-drawings of ordered rooted binary trees and near-linear area drawings of outerplanar graph

We study a family of algorithms, introduced by Chan [SODA 1999], for drawing ordered rooted binary trees. Any algorithm in this family (which we name an LR-algorithm) takes in input an ordered rooted binary tree T with a root rT ,and recursively constructs drawings T L of the left subtree L of rT and TR of the right subtree R of rT ; then either it applies the left rule, i.e., it places L one unit below and to the left of rT , and R one unit below L with the root of R vertically aligned with rT , or it applies the right rule, it places R one unit below and to the right of rT , and L one unit below R with the root of L vertically aligned with rT . In both cases, the edges between rT and its children are represented by straight-line segments. Different LRalgorithms result from different choices on whether the left or right rule is applied at any node of T. We are interested in constructing LR-drawings (that are drawings obtained via LR-algorithms) with small width. Chan showed three LRalgorithms that achieve, for an n-node ordered rooted binary tree, width O(n0:695), width O(n0:5), and width O(n0:48). We prove that, for every n-node ordered rooted binary tree, an LR-drawing with minimum width can be constructed in O(n1:48) time. Further, we show an infi- nite family of n-node ordered rooted binary trees requiring (nO:418) width in any LR-drawing; no lower bound better than (log n) was previously known. Finally, we present the results of an experimental evaluation that allowed us to determine the minimum width of all the ordered rooted binary trees with up to 455 nodes. Our interest in LR-drawings is mainly motivated by a result of Di Battista and Frati [Algorithmica 2009], who proved that n-vertex outerplanar graphs have outerplanar straight-line drawings in O(n1:48) area by means of a drawing algorithm which resembles an LR-algorithm. We deepen the connection between LR-drawings and outerplanar drawings by proving that, if n-node ordered rooted binary trees have LR-drawings with f(n) width, for any function f(n), then n-vertex outerplanar graphs have outerplanar straight-line drawings in O(f(n)) area. Finally, we exploit a structural decomposition for ordered rooted binary trees introduced by Chan in order to prove that every n-vertex outerplanar graph has an outerplanar straight-line drawing in O (n 2 p 2 log2 np log n) area.