On Compatible Matchings

Oswin Aichholzer, Alan Arroyo, Zuzana Masárová, Irene Parada, Daniel Perz, Alexander Pilz, Josef Tkadlec, Birgit Vogtenhuber

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


A matching is compatible to two or more labeled point sets of size n with labels { 1, ⋯, n} if its straight-line drawing on each of these point sets is crossing-free. We study the maximum number of edges in a matching compatible to two or more labeled point sets in general position in the plane. We show that for any two labeled convex sets of n points there exists a compatible matching with ⌊2n⌋ edges. More generally, for any ℓ labeled point sets we construct compatible matchings of size Ω(n 1 / ). As a corresponding upper bound, we use probabilistic arguments to show that for any ℓ given sets of n points there exists a labeling of each set such that the largest compatible matching has O(n 2 / ( + 1 )) edges. Finally, we show that Θ(log n) copies of any set of n points are necessary and sufficient for the existence of a labeling such that any compatible matching consists only of a single edge.

Original languageEnglish
Title of host publicationWALCOM
Subtitle of host publicationAlgorithms and Computation - 15th International Conference and Workshops, WALCOM 2021, Proceedings
EditorsRyuhei Uehara, Seok-Hee Hong, Subhas C. Nandy
Number of pages13
Publication statusPublished - 2021

Publication series

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


  • Compatible graphs
  • Crossing-free matchings
  • Geometric graphs

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'On Compatible Matchings'. Together they form a unique fingerprint.
  • On Compatible Matchings

    Daniel Perz (Speaker)


    Activity: Talk or presentationTalk at conference or symposiumScience to science

Cite this