Torsten Ueckerdt (KIT): Flipping Non-Crossing Spanning Trees on Convex Point Sets

Abstract:
We consider the non-crossing straight-line spanning trees on a finite point set in the plane. A
flip is a transformation of one such tree into another by means of exchanging exactly one edge.
In this talk we consider the flip graph whose vertices are the non-crossing trees and edges are the
flips.
In particular we are interested in the case of n points in convex position and the diameter of the
corresponding flip graph in terms of n.
We present improved upper and lower bounds of 14/9 n and 5/3 n, respectively.
This is a joint work with Havard Bjerkevik, Linda Kleist and Birgit Vogtenhuber.

Vor diesem Vortrag, ab 16.45 Uhr, gibt es wieder Kaffee und Tee im Raum 1404.
Es sind alle herzlich dazu eingeladen.

gez. Prof. Dr. Torsten Mütze