Tree Drawings Revisited

2018/03/19 by Timothy M. Chan, Chan, Timothy M. · 1 citation
Computer Science · #Advanced Graph Theory Research #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Constraint Satisfaction and Optimization #FOS: Computer and information sciences

paper · pdf · doi:10.48550/arxiv.1803.07185

openalex publication_date 2018/03/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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(√(loglog nlogloglog n))}, improving the longstanding O(nlog n) bound; 2. every tree of size n (with arbitrarily large degree) has a straight-line upward drawing with area n√(log n)(loglog n)^O(1), improving the longstanding O(nlog 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(nloglog n) bound by Shin, Kim, and Chwa (1996) and Chan, Goodrich, Kosaraju, and Tamassia (1996); 4. every binary tree of size n has a straight-line order-preserving drawing with area n2^{O(log^*n)}, improving the previous O(nloglog n) bound by Garg and Rusu (2003); 5. every binary tree of size n has a straight-line orthogonal order-preserving drawing with area n2^{O(√(log n))}, improving the O(n^3/2) previous bound by Frati (2007).

Cited by

• Straight-line Orthogonal Drawing of Complete Ternary Tree Requires O(n^1.032) Area

Related

• On Upward Drawings of Trees on a Given Grid
• On the Area Requirements of Planar Straight-Line Orthogonal Drawings of Ternary Trees
• Improved Upper and Lower Bounds for LR Drawings of Binary Trees
• Straight-line Orthogonal Drawing of Complete Ternary Tree Requires O(n^1.032) Area
• Ideal Tree-drawings of Approximately Optimal Width (And Small Height)