Reconfiguration of Triangulations of a Planar Point Set

In a reconfiguration problem, the goal is to change an initial configuration of some structure to a final configuration using some limited set of moves. Examples include: sorting a list by swapping pairs of adjacent elements; finding the edit distance between two strings; or solving a Rubik’s cube in a minimum number of moves. Central questions are: Is reconfiguration possible? How many moves are required?

In this talk I will survey some reconfiguration problems, and then discuss the case of triangulations of a point set in the plane. A move in this case is a flip that replaces one edge by the opposite edge of its surrounding quadrilateral when that quadrilateral is convex. In joint work with Zuzana Masárová and Uli Wagner we characterize when one edge-labelled triangulation can be reconfigured to another via flips. The proof involves combinatorics, geometry, and topology.

Anna Lubiw is a professor in the Cheriton School of Computer Science, University of Waterloo. She has a PhD from the University of Toronto (1986) and a Master of Mathematics degree from the University of Waterloo (1983).

Her research is in the areas of Computational Geometry, Graph Drawing and Graph Algorithms. She was named the Ross and Muriel Cheriton Faculty Fellow in 2014, received the University of Waterloo outstanding performance award in 2012 and was named a Distinguished Scientist by the Association for Computing Machinery in 2009. She serves on the editorial boards of the Journal of Computational Geometry and the Journal of Graph Algorithms and Applications.