On the Area Requirements of Straight-Line Orthogonal Drawings of Ternary Trees

摘要

We prove that every n-node ternary tree has a planar straight-line orthogonal drawing in O(nl~(1,576)) area, improving upon the previously best known O(n~(1,631)) bound. Further, we present an upper bound, the outcomes of an experimental evaluation, and a conjecture on the area requirements of planar straight-line orthogonal drawings of complete ternary trees.