Transformed flips in triangulations and matchings

O. Aichholzer, L. Andritsch, K. Baur, and B. Vogtenhuber

Abstract:

Plane perfect matchings of $2n$ points in convex position are in bijection with triangulations of convex polygons of size $n+2$. Edge flips are a classic operation to perform local changes both structures have in common. In this work, we use the explicit bijection from Aichholzer et al. (2018) to determine the effect of an edge flip on the one side of the bijection to the other side, that is, we show how the two different types of edge flips are related. Moreover, we give an algebraic interpretation of the flip graph of triangulations in terms of elements of the corresponding Temperley-Lieb algebra.

Reference: O. Aichholzer, L. Andritsch, K. Baur, and B. Vogtenhuber. Transformed flips in triangulations and matchings. submitted, pages 1-17, 2019.