@inproceedings{1f3b70c60af14415a76fe27111936448,
title = "Perfect Matchings with Crossings",
abstract = "For sets of n= 2 m 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 Cm different plane perfect matchings, where Cm 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≤164n2-O(nn), any set of 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 fewer than 572n2 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, Order types, Perfect matchings",
author = "Oswin Aichholzer and Ruy Fabila-Monroy and Philipp Kindermann and Irene Parada and Rosna Paul and Daniel Perz and Patrick Schnider and Birgit Vogtenhuber",
note = "Publisher Copyright: {\textcopyright} 2022, Springer Nature Switzerland AG.; 33<sup>rd</sup> International Workshop on Combinatorial Algorithms, IWOCA 2022 ; Conference date: 07-06-2022 Through 09-06-2022",
year = "2022",
doi = "10.1007/978-3-031-06678-8_4",
language = "English",
isbn = "978-3-031-06677-1",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer",
pages = "46--59",
editor = "Cristina Bazgan and Henning Fernau",
booktitle = "Combinatorial Algorithms",
}