Flips in Odd Matchings

O. Aichholzer, A. Brötzner, D. Perz, and P. Schnider

Abstract:

Let $\mathcal{P}$ be a set of $n=2m+1$ points in the plane in general position. We define the graph $GM_\mathcal{P}$ whose vertex set is the set of all plane matchings on $\mathcal{P}$ with exactly $m$ edges. Two vertices in $GM_\mathcal{P}$ are connected if the two corresponding matchings have $m-1$ edges in common. In this work we show that $GM_\mathcal{P}$ is connected.

Reference: O. Aichholzer, A. Brötzner, D. Perz, and P. Schnider. Flips in odd matchings. In Proceedings of the 36th Canadian Conference on Computational Geometry (CCCG 2024), pages 299-303, 2024.