Perfect Matchings with Crossings

Algorithmica. 2024;86(3):697-716. doi: 10.1007/s00453-023-01147-7. Epub 2023 Jul 18.

Abstract

For sets of n points, n even, 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 Cn/2 different plane perfect matchings, where Cn/2 is the n/2-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 k164n2-3532nn+122564n, any set with n points, n sufficiently large, admits a perfect matching with exactly k crossings. (2) There exist sets of n points where every perfect matching has at most 572n2-n4 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 n/22 crossings and with n/22-1 crossings.

Keywords: Combinatorial geometry; Crossings; Geometric graphs; Order types; Perfect matchings.