Bichromatic Perfect Matchings with Crossings

Abstract

We consider bichromatic point sets with $n$ red and $n$ blue points and study straight-line bichromatic perfect matchings on them. We show that every such point set in convex position admits a matching with at least $\frac{3n^2}{8}-\frac{n}{2}+c$ crossings, for some $-\frac{1}{2}\le c\le \frac{1}{8}$. This bound is tight since for any $k>\frac{3n^2}{8}-\frac{n}{2}+\frac{1}{8}$ there exist bichromatic point sets that do not admit any perfect matching with $k$ crossings.

Appears in the Proceedings of the 31st International Symposium on Graph Drawing and Network Visualization (GD 2023)