In this paper we investigate the structure of a flip graph on non-crossing perfect matchings in the plane. Consider the set of all non-crossing straight-line perfect matchings on a set of 2n points that are placed equidistantly on the unit circle. The graph \mathcal{H matching edges that span an empty quadrilateral with the other two edges of the quadrilateral, provided that the quadrilateral contains the center of the unit circle.  We show that the graph H_n is connected for odd n, but has exponentially many small connected components for even n, which we characterize and count via Catalan and generalized Narayana numbers. For odd n, we also prove that the diameter of H_n is linear in n. Furthermore, we determine the minimum and maximum degree of H_n for all n, and characterize and count the corresponding vertices. Our results imply the non-existence of certain rainbow cycles  , and they answer several open questions and conjectures raised in a recent paper by Felsner, Kleist, M\"utze, and Sering.
In this paper we investigate the structure of flip graphs on non-crossing perfect matchings in the plane. Specifically, consider all non-crossing straight-line perfect matchings on a set of 2n points that are placed equidistantly on the unit circle. A flip operation on such a matching replaces two matching edges that span an empty quadrilateral with the other two edges of the quadrilateral, and the flip is called centered if the quadrilateral contains the center of the unit circle. The graph \mathcal{G We show that the graph H_n is connected for odd n, but has exponentially many small connected components for even n, which we characterize and count via Catalan and generalized Narayana numbers. For odd n, we also prove that the diameter of H_n is linear in n. Furthermore, we determine the minimum and maximum degree of H_n for all n, and characterize and count the corresponding vertices. Our results imply the non-existence of certain rainbow cycles in \mathcal{G , and they resolve several open questions and conjectures raised in a recent paper by Felsner, Kleist, M\"utze, and Sering.
R
a flip graph
flip graphs
R
Consider the set of
Specifically, consider
R
The graph \mathcal{H
A flip operation on such a matching replaces two
R
provided that the
and the flip is called centered if the
A
The graph \mathcal{G
A
in \mathcal{G
R
answer
resolve