Perfect Matchings with Crossings

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Documents

  • Fulltext

    Submitted manuscript, 563 KB, PDF document

  • 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.

Original languageEnglish
Title of host publicationCombinatorial Algorithms - 33rd International Workshop, IWOCA 2022, Proceedings
EditorsCristina Bazgan, Henning Fernau
PublisherSpringer
Publication date2022
Pages46-59
ISBN (Print)9783031066771
DOIs
Publication statusPublished - 2022
Event33rd International Workshop on Combinatorial Algorithms, IWOCA 2022 - Trier, Germany
Duration: 7 Jun 20229 Jun 2022

Conference

Conference33rd International Workshop on Combinatorial Algorithms, IWOCA 2022
LandGermany
ByTrier
Periode07/06/202209/06/2022
SeriesLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13270 LNCS
ISSN0302-9743

Bibliographical note

Publisher Copyright:
© 2022, Springer Nature Switzerland AG.

    Research areas

  • Combinatorial geometry, Crossings, Order types, Perfect matchings

ID: 318812224