Discrete Mathematics and Optimization Seminar

University of Tuebingen
Wednesday March 24th at 4.30pm
McConnell 320

Title. A Quadratic Distance Bound on Sliding between Crossing-free Spanning Trees.

Abstract. 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.