Oct 14, 2016:
Drawing Trees with Low Ply Number
Timothy Johnson
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.