ICS Theory Group

Winter 2017: Theory Seminar
Bren Hall, Room 1300, 1:00pm


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.