Compatible Geometric Matchings

Abstract

This paper studies non-crossing geometric perfect matchings. Two such perfect matchings are \emph{compatible} if they have the same vertex set and their union is also non-crossing. Our first result states that for any two perfect matchings $M$ and $M^{\prime }$ of the same set of $n$ points, for some $k\in\Oh{\log n}$, there is a sequence of perfect matchings $M=M_0,M_1,...,M_k=M^{\prime }$, such that each $M_i$ is compatible with $M_{i+1}$. This improves the previous best bound of $k\le n-2$. We then study the conjecture: \emph{every perfect matching with an even number of edges has an edge-disjoint compatible perfect matching}. We introduce a sequence of stronger conjectures that imply this conjecture, and prove the strongest of these conjectures in the case of perfect matchings that consist of vertical and horizontal segments. Finally, we prove that every perfect matching with $n$ edges has an edge-disjoint compatible matching with approximately $4n/5$ edges.

improved exposition and improved results

Cited by in corpus (10)

• Quasi-Parallel Segments and Characterization of Unique Bichromatic Matchings
• Flip Distance to a Non-crossing Perfect Matching
• Bottleneck Non-Crossing Matching in the Plane
• Linear transformation distance for bichromatic matchings
• Conflict-free graph orientations with parity constraints
• Non-Crossing Perfect Matchings and Triangle-Free Geometric Graphs
• Structural Properties of Bichromatic Non-crossing Matchings
• Flip Distance to some Plane Configurations
• Plane augmentation of plane graphs to meet parity constraints
• On Compatible Matchings