**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*^{2}) 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*^{2} log n)
operations was conjectured.