## February 10, 2017:

#
LR-Drawings of Ordered Rooted Binary Trees

##
Timothy Johnson

Drawing from papers
by Chan (SODA
1999) and Frati
et. al. (SODA 2017), we study both heuristics and exact algorithms
for constructing LR-drawings of ordered rooted binary trees with small
width. We prove an upper bound for the width of these drawings of
$O(n^{0.48})$, and a lower bound of $\Omega(n^{0.418})$. Then we present
an exact algorithm that can efficiently compute the maximum width
required for a given tree, and show how it can be used to find the
maximum width required for all trees of a given size. After computing
the maximum width requirement for trees with up to several hundred
nodes, we conclude that both the upper and lower bounds are likely not
tight. Lastly, by extending the allowed operations for LR-drawings, we
show that we can achieve sub polynomial width.