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

作者：Aichholzer Oswin^*; Asinowski Andrei; Miltzow Tillmann

来源：Electronic Journal of Combinatorics, 2015, 22(1): P1.65.

DOI：10.37236/4403

• Planar straight-line graphs
• disjoint compatible matchings
• reconfiguration graph
• non-crossing geometric drawings
• non-crossing partitions
• combinatorial enumeration

Let X-2k be a set of 2k labeled points in convex position in the plane. We consider geometric non-ntersecting straight-line perfect matchings of X-2k. Two such matchings, M and M', are disjoint compatible if they do not have common edges, and no edge of M crosses an edge of M'. Denote by DCMk 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 >= 9, the connected components of DCMk 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.

• 出版日期2015-3-13