Perfect Matchings with Crossings

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningfagfællebedømt

Dokumenter

  • Fulltext

    Indsendt manuskript, 563 KB, PDF-dokument

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

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.

OriginalsprogEngelsk
TitelCombinatorial Algorithms - 33rd International Workshop, IWOCA 2022, Proceedings
RedaktørerCristina Bazgan, Henning Fernau
ForlagSpringer
Publikationsdato2022
Sider46-59
ISBN (Trykt)9783031066771
DOI
StatusUdgivet - 2022
Begivenhed33rd International Workshop on Combinatorial Algorithms, IWOCA 2022 - Trier, Tyskland
Varighed: 7 jun. 20229 jun. 2022

Konference

Konference33rd International Workshop on Combinatorial Algorithms, IWOCA 2022
LandTyskland
ByTrier
Periode07/06/202209/06/2022
NavnLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Vol/bind13270 LNCS
ISSN0302-9743

Bibliografisk note

Funding Information:
Keywords: Perfect matchings · Crossings · Combinatorial geometry · Order types Research on this work has been 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 73499 - CONNECT. O. A. and R. P. supported by FWF grant W1230. R. M. partially supported by CONA-CYT(Mexico) grant 253261. P. S. supported by ERC Grant ERC StG 716424-CASe. D. P., I. P., and B. V. supported by FWF Project I 3340-N35. Some results of this work have been presented at the “Computational Geometry: Young Researchers Forum” in 2021 [2].

Publisher Copyright:
© 2022, Springer Nature Switzerland AG.

ID: 318812224