Back

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

@Mathematics
  • Date: 11/12/2024
  • Time: 17:15
  • Place: Raum 1403

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.


Before this lecture, from 4:45 p.m., there will be coffee and tea again in room 1404. Everyone is warmly invited to attend.


gez. Prof. Dr. Torsten Mütze

Related Links