Disjoint Compatibility Graph of Non-Crossing Matchings of Points in Convex Position

  • Oswin Aichholzer Institut für Softwaretechnologie, Technische Universität Graz
  • Andrei Asinowski Institut für Informatik, Freie Universität Berlin
  • Tillmann Miltzow Institut für Informatik, Freie Universität Berlin
Keywords: Planar straight-line graphs, disjoint compatible matchings, reconfiguration graph, non-crossing geometric drawings, non-crossing partitions, combinatorial enumeration.

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'$, are disjoint compatible if they do not have common edges, and no edge of $M$ crosses an edge of $M'$. Denote by $\rm{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 \geq 9$, the connected components of $\rm{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.
Published
2015-03-13
Article Number
P1.65