Perfect Matchings with Crossings

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

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference paperpeer-review


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 C m different plane perfect matchings, where C m 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
Subtitle of host publication33rd International Workshop, IWOCA 2022, Trier, Germany, June 7–9, 2022, Proceedings
EditorsCristina Bazgan, Henning Fernau
Place of PublicationCham
Number of pages14
ISBN (Electronic)978-3-031-06678-8
ISBN (Print)978-3-031-06677-1
Publication statusPublished - 2022
Event33rd International Workshop on Combinatorial Algorithms: IWOCA 2022 - Trier, Germany
Duration: 7 Jun 20229 Jun 2022

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13270 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference33rd International Workshop on Combinatorial Algorithms


  • Perfect matchings
  • crossings
  • Combinatorial geometry
  • Order types
  • Crossings

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fields of Expertise

  • Information, Communication & Computing
  • Perfect Matchings with crossings

    Rosna Paul (Speaker)

    7 Jun 20229 Jun 2022

    Activity: Talk or presentationTalk at conference or symposiumScience to science

Cite this