Flip distance in plane perfect bichromatic matching

Carleton University

Given two plane perfect bichromatic matchings $M$ and $M'$ on the same point set, we show that there exists a sequence of plane perfect matchings $M=M_0, M_1, M_2, \dots, M_k=M'$ where each consecutive pair of matchings is compatible (i.e., their union is plane) and $k$ is $O(n)$.