Fall 2016: Theory Seminar
DBH, Room 1300, 1:00pm

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.

1. 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.
2. 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.