|Discrete Mathematics and Optimization Seminar
University of Tuebingen
Wednesday March 24th at 4.30pm
Title. A Quadratic Distance Bound on Sliding between Crossing-free Spanning Trees.
Let S be a set of n points in the plane in general position and
let &TauS be the set of all crossing-free spanning trees of S.
We show that it is possible to transform any two trees in &TauS
into each other by O(n2) local and constant-size edge slide operations.
Previously Avis and Fukuda have shown that the corresponding tree graph is
connected but no polynomial upper bound for this
task was known; in [Aichholzer-Aurenhammer-Hurtado] a bound of O(n2 log n)
operations was conjectured.