In SODA'99, Chan introduced a simple type of planar straight-line upward order-preserving drawings of binary trees, known as LR drawings: such a drawing is obtained by picking a root-to-leaf path, drawing the path as a straight line, and recursively drawing the subtrees along the paths. Chan proved that any binary tree with n nodes admits an LR drawing with O(n~(0.48)) width. In SODA'17, Frati, Patrignani, and Roselli proved that there exist families of n-node binary trees for which any LR drawing has Ω(n~(0.418)) width. In this paper, we improve Chan's upper bound to O(n~(0.437)) and Frati et al.'s lower bound to Ω(n~(0.429)).
展开▼
