2015/02/10 by Thérèse Biedl, Biedl, Therese
Computer Science · Environmental Science · #Computational Geometry and Mesh Generation #Remote Sensing and LiDAR Applications #Data Management and Algorithms
paper · pdf · doi:10.48550/arxiv.1502.02753
For rooted trees, an ideal drawing is one that is planar, straight-line, strictly-upward, and order-preserving. This paper considers ideal drawings of rooted trees with the objective of keeping the width of such drawings small. It is not known whether finding the minimum-possible width is NP-hard or polynomial. This paper gives a 2-approximation for this problem, and a 2Δ-approximation (for Δ-ary trees) where additionally the height is O(n). For trees with Δ≤ 3, the former algorithm finds ideal drawings with minimum-possible width.