Oswin Aichholzer and Joseph Dorfer (TU Graz): Flips in Plane Graphs

Link:
https://uni-kassel.zoom-x.de/j/62114766919?pwd=TwdVfoGuQPbTrHij2KP2WP5DubXa4x.1

Abstract:
Reconfiguration is the process of changing a structure into another - either through continuous
motion or through discrete changes. We concentrate on plane graphs and discrete reconfiguration
steps of bounded complexity, so-called flips. A flip exchanges one or two edge(s) of the graph for
one or two other edge(s), such that the resulting graph is of the same class of graphs (matchings,
triangulations, trees, paths, . . . ).
The flip graph is defined as the graph having a vertex for each configuration (in our case for each
plane graph of a certain type) and an edge for each flip between them. Three questions are central:
studying the connectivity of the flip graph, its diameter, and the complexity of finding the shortest
path between two given configurations. Many classic and new results are known, for example for
flips in triangulations or the transformation of plane spanning trees. We will give an overview of
these results and mention several (old and new) open problems in this area, with a focus on recent
developments for trees.

gez. Prof. Dr. Torsten Mütze