Oct 14, 2016:
Drawing Trees with Low Ply Number
Abstract: Ply number has been recently introduced as a criterion for graph
drawing. I solve two open problems in drawing trees with low ply number.
- For any Delta, there is a value of alpha such that we can draw any tree with maximum degree Delta with an alpha-ply number of 1. Previously, this had only been studied for trees with degree 3.
For any Delta, we can draw trees of maximum degree Delta with O(log n) ply number in polynomial area. Previously, this was only possible for trees with maximum degree 6.