Discrete Mathematics and Optimization Seminar

---

KLAUS REINHARDT
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 &Tau_S be the set of all crossing-free spanning trees of S.
We show that it is possible to transform any two trees in &Tau_S into each other by O(n²) 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(n² log n) operations was conjectured.