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

2025/06/10 by Bui, Hong Duc
#Computational Geometry (cs.CG) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2506.09269

Abstract

We resolve a conjecture posed by Covella, Frati and Patrignani by proving the straight-line orthogonal drawing of the complete ternary tree with n nodes satisfying the subtree separation property with smallest area has area Ω(n^1.031). We also improve the upper bound of this area to O(n^1.032).

Citations

• On the Area Requirements of Planar Straight-Line Orthogonal Drawings of Ternary Trees
• Tree Drawings Revisited

Related

• On the Area Requirements of Planar Straight-Line Orthogonal Drawings of Ternary Trees
• Tree Drawings Revisited
• Counting ternary trees according to the number of middle edges and factorizing into (3/2)-ary trees
• Small-Area Orthogonal Drawings of 3-Connected Graphs
• Improved Upper and Lower Bounds for LR Drawings of Binary Trees