Perfect Matchings with Crossings

Note: Please see pdf for full abstract with equations. For sets of $n=2m$ points in general position in the plane we consider straight-line drawings of perfect matchings on them. It is well known that such sets admit at least $C_m$ different plane perfect matchings, where $C_m$ is the $m$-th Catalan number. Generalizing this result we are interested in the number of drawings of perfect matchings which have $k$ crossings. We show the following results. (1)~For every $k\leq \frac{1}{64}n^2-O(n \sqrt{n})$, any set with an even number of $n$ points, $n$ sufficiently large, admits a perfect matching with exactly $k$ crossings. (2)~There exist sets of $n$ points ($n$ even) where every perfect matching has fewer than $\frac{5}{72}n^2$ crossings. (3)~The number of perfect matchings with at most $k$ crossings is superexponential in $n$ if $k$ is superlinear in $n$. (4)~Point sets in convex position minimize the number of perfect matchings with at most $k$ crossings for $k=0,1,2$, and maximize the number of perfect matchings with $\binom{n/2}{2}$ crossings and with ${\binom{n/2}{2}}\!-\!1$ crossings.