LR-Drawings of Ordered Rooted Binary Trees and Near-Linear Area Drawings of Outerplanar Graphs

摘要

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 O(n·2~({the square root of}(2 log_2 n)) {the square root of}(log n)) area.