Perfect Matchings with Crossings

Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt

Dokumenter

  • Fulltext

    Forlagets udgivne version, 622 KB, PDF-dokument

  • Oswin Aichholzer
  • Ruy Fabila-Monroy
  • Philipp Kindermann
  • Irene Parada
  • Rosna Paul
  • Daniel Perz
  • Patrick Schnider
  • Birgit Vogtenhuber

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 k≤164n2-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.

OriginalsprogEngelsk
TidsskriftAlgorithmica
Vol/bind86
Sider (fra-til)697–716
ISSN0178-4617
DOI
StatusUdgivet - 2024

Bibliografisk note

Funding Information:
Research on this work was initiated at the 16th European Research Week on Geometric Graphs which was held from November 18 to 22, 2019, near Strobl (Austria). We thank all participants for the good atmosphere as well as for discussions on the topic. Further, we thank Clemens Huemer for bringing this problem to our attention in the course of a meeting of the H2020-MSCA-RISE Project 734922 - CONNECT. O. A. and R. P. supported by FWF Grant W1230. P. S. supported by ERC Grant ERC StG 716424-CASe. D. P., I. P., and B. V. supported by FWF Project I 3340-N35. I. P. supported by the Independent Research Fund Denmark Grant 2020-2023 (9131-00044B) “Dynamic Network Analysis” and by the Margarita Salas Fellowship funded by the Ministry of Universities of Spain and the European Union (NextGenerationEU).

Funding Information:
Open access funding provided by Austrian Science Fund (FWF). Nothing other than that in Acknowledgements.

Publisher Copyright:
© 2023, The Author(s).

ID: 360263031