PIMS-UManitoba Distinguished Colloquium: Birgit Vogtenhuber

The reconfiguration of one discrete structure into another one, through a sequence small local modifications, is a wide research area. Famous topics of study range from games like the Rubik's cube or the 15-puzzle via robot motion planning to rotations in binary trees and edge flips in triangulations or other plane geometric graphs.

Many algorithmic questions arise naturally for discrete reconfiguration processes: Can (any) two structures be reconfigured into one another? If yes, how many reconfiguration steps are (sometimes) needed? And what is the algorithmic complexity of finding a short(est) reconfiguration sequence for two given structures?

In this lecture, we will report on the reconfiguration problem for spanning trees on graphs and non-crossing geometric spanning trees on point sets. A flip sequence between two (non-crossing) spanning trees (on a point set or graph) is a sequence single edge exchanges (possibly with restrictions) such that each intermediate structure is again a (non-crossing) spanning tree (on the point set or graph). It is well known that any two (non-crossing) spanning trees (on a point set or graph) can be transformed into each other with a finite number of flips.

We will review old and recent results concerning bounds on the number of flips that are sometimes required and always sufficient. Further, we will discuss properties of shortest flip sequences between spanning trees as well as algorithmic questions, and briefly report on a very recent complexity result on shortest flip sequences for other structures that arose from the study of flips in spanning trees. We will close with various open problems.