Improved Upper and Lower Bounds for LR Drawings of Binary Trees

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

No reviews yet.

No comments yet.