Combinatorics of perfect matchings in plane bipartite graphs and application to tilings

AbstractLet G be a plane bipartite graph which admits a perfect matching and with distinguished faces called holes. Let MG denote the perfect matchings graph: its vertices are the perfect matchings of G, two of them being joined by an edge, if and only if they differ only on an alternating cycle bounding a face which is not a hole. We solve the following problem: Find a criterion for two perfect matchings of G to belong to the same connected component of MG, and in particular determine in which case MG is connected. The motivation of this work is a result on tilings of Saldanha et al. (Comput. Geom. 14 (1995) 207)