How to Fit a Tree in a Box

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

slides

Journal Article (peer-reviewed)

Conference Proceedings (peer-reviewed)

Archived Publication (not reviewed)

back to list