Perfect Matchings with Crossings

Research output: Contribution to journalJournal articleResearchpeer-review

Documents

  • Fulltext

    Final published version, 622 KB, PDF document

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

Original languageEnglish
JournalAlgorithmica
Volume86
Pages (from-to)697–716
ISSN0178-4617
DOIs
Publication statusPublished - 2024

Bibliographical note

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

    Research areas

  • Combinatorial geometry, Crossings, Geometric graphs, Order types, Perfect matchings

ID: 360263031