Tree Drawings Revisited
- PDF / 684,710 Bytes
- 22 Pages / 439.37 x 666.142 pts Page_size
- 22 Downloads / 212 Views
Tree Drawings Revisited Timothy M. Chan1 Received: 31 December 2018 / Revised: 10 May 2019 / Accepted: 22 May 2019 © Springer Science+Business Media, LLC, part of Springer Nature 2019
Abstract We make progress on a number of open problems concerning the area requirement for drawing trees on a grid. We prove that (1) every tree of size n (with arbitrarily large √ degree) has a straight-line drawing with area n2 O( log log n log log log n) , improving the longstanding O(n log n) bound; (2) every tree of√size n (with arbitrarily large degree) has a straight-line upward drawing with area n log n(log log n) O(1) , improving the longstanding O(n log n) bound; (3) every binary tree of size n has a straight-line ∗ orthogonal drawing with area n2 O(log n) , improving the previous O(n log log n) bound; (4) every binary tree of size n has a straight-line order-preserving drawing with ∗ area n2 O(log n) , improving the previous O(n log log n) bound; (5) every binary√tree of size n has a straight-line orthogonal order-preserving drawing with area n2 O( log n) , improving the previous O(n 3/2 ) bound. Keywords Graph drawing · Trees · Recursion Mathematics Subject Classification 05C05 · 68R10 · 68U05 · 68Q25
1 Introduction Drawing graphs with small area has been a subject of intense study in combinatorial and computational geometry for more than two decades [11,12]. The goal is to determine worst-case bounds on the area needed to draw any n-vertex graph in a given class, subject to certain drawing criteria, where vertices are mapped to points on an integer
Editor in Charge: Kenneth Clarkson A preliminary version of this paper appeared in Proc. 34th Symposium on Computational Geometry (SoCG), 23:1–23:15, 2018. Timothy M. Chan [email protected] 1
Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, IL 61801, USA
123
Discrete & Computational Geometry
grid {1, . . . , W } × {1, . . . , H }, and the area of the drawing is defined to be the width W times the height H . All drawings in this paper are required to be planar, where edge crossings are not allowed. All our results will be about straight-line drawings, where edges are drawn as straight line segments, although poly-line drawings that allow bends along the edges have also received considerable attention. It is well known [10,23] that every planar graph of size n has a straight-line drawing with area O(n 2 ) (with width and height O(n)), and this bound is asymptotically tight in the worst case. Much research is devoted to understanding which subclasses of planar graphs admit subquadratic-area drawings, and obtaining tight area bounds for such classes. 1.1 Drawing Arbitrary Trees Among the simplest is the class of all trees. As hierarchical structures occur naturally in many areas (from VLSI design to phylogeny), visualization of trees is of particular interest. Although there have been numerous papers on tree drawings (e.g., [2,4–9,13– 20,22,24–28]), the most basic question of determining the worst-case area needed to draw arbitrary trees, w
Data Loading...
