Flips in Odd Matchings

Abstract

Let $\mathcal{P}$ be a set of $n=2m+1$ points in the plane in general position. We define the graph $G{M}_{\mathcal{P}}$ whose vertex set is the set of all plane matchings on $\mathcal{P}$ with exactly $m$ edges. Two vertices in $G{M}_{\mathcal{P}}$ are connected if the two corresponding matchings have $m-1$ edges in common. In this work we show that $G{M}_{\mathcal{P}}$ is connected and give an upper bound of $O(n^2)$ on its diameter. Moreover, we present a tight bound of $\hat{I}˜(n)$ for the diameter of the flip graph of points in convex position.

Appeared in CCCG2024