Improved Upper and Lower Bounds for LR Drawings of Binary Trees

Abstract

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 $\Omega (n^{0.418})$ width. In this note, we improve Chan's upper bound to $O(n^{0.437})$ and Frati et al.'s lower bound to $\Omega (n^{0.429})$.

Appears in the Proceedings of the 28th International Symposium on Graph Drawing and Network Visualization (GD 2020)