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

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 $\Omega (n^{1.031})$. We also improve the upper bound of this area to $O(n^{1.032})$.

7 pages, 4 figures