Disjoint compatibility graph of non-crossing matchings of points in convex position

Abstract

Let $X_{2k}$ be a set of $2k$ labeled points in convex position in the plane. We consider geometric non-intersecting straight-line perfect matchings of $X_{2k}$. Two such matchings, $M$ and $M^{\prime }$, are disjoint compatible if they do not have common edges, and no edge of $M$ crosses an edge of $M^{\prime }$. Denote by ${\mathrm{DCM}}_k$ the graph whose vertices correspond to such matchings, and two vertices are adjacent if and only if the corresponding matchings are disjoint compatible. We show that for each $k\ge 9$, the connected components of ${\mathrm{DCM}}_k$ form exactly three isomorphism classes -- namely, there is a certain number of isomorphic small components, a certain number of isomorphic medium components, and one big component. The number and the structure of small and medium components is determined precisely.

46 pages, 30 figures