Center for Algorithms and Theory of Computation

CS 269S, Fall 2018: Theory Seminar
Bren Hall, Room 1423, 1pm


October 26, 2018:

How to Fit a Tree in a Box

Martha Osegueda

We study compact straight-line embeddings of trees. We show that perfect binary trees can be embedded optimally: a tree with $n$ nodes can be drawn on a $\sqrt{n}\times \sqrt{n}$ grid. We also show that testing whether a given binary tree has an upward embedding with a given combinatorial embedding in a given grid is NP-hard.

(Based on a paper by Hugo A. Akitaya, Maarten Löffler, and Irene Parada from Graph Drawing 2018.)