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  r   T  , and recursively constructs drawings Γ  L   of the left subtree  L  of  r   T   and Γ  R   of the right subtree  R  of  r T  ; then either it applies the  left rule , i.e., it places Γ  L   one unit below and to the left of  r T  , and Γ  R   one unit below Γ  L   with the root of  R  vertically aligned with  r T  , or it applies the  right rule , i.e., it places Γ  R   one unit below and to the right of  r T  , and Γ  L   one unit below Γ  R   with the root of  L  vertically aligned with  r T  . In both cases, the edges between  r T   and its children are represented by straight-line segments. Different LR-algorithms 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 LR-algorithms that achieve, for an  n -node ordered rooted binary tree, width  O ( n  0.695 ), width  O ( n  0.5 ), and width  O ( n  0.48 ).   We prove that, for every  n -node ordered rooted binary tree, an LR-drawing with minimum width can be constructed in  O ( n  1.48 ) time. Further, we show an infinite family of  n -node ordered rooted binary trees requiring Ω( n  0.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 ( n  1.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 outer-planar straight-line drawing in [EQUATION] area.
['Fabrizio Frati', 'Maurizio Patrignani', 'Vincenzo Roselli']
LR-drawings of ordered rooted binary trees and near-linear area drawings of outerplanar graphs