On Compatible Matchings

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

Publikation: Beitrag in einer FachzeitschriftArtikelBegutachtung

Abstract

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 sets of n points in convex position there exists a compatible matching with ⌊2n + 1 − 1⌋ edges. More generally, for any ℓ labeled point sets we construct compatible matchings of size Ω(n1/ℓ). 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(n2/(ℓ+1)) edges. Finally, we show that Θ(log n) copies of any set of n points are necessary and sufficient for the existence of labelings of these point sets such that any compatible matching consists only of a single edge.

Originalspracheenglisch
Seiten (von - bis)225-240
Seitenumfang16
FachzeitschriftJournal of Graph Algorithms and Applications
Jahrgang26
Ausgabenummer2
DOIs
PublikationsstatusVeröffentlicht - 2022

ASJC Scopus subject areas

  • Theoretische Informatik
  • Allgemeine Computerwissenschaft
  • Angewandte Informatik
  • Geometrie und Topologie
  • Theoretische Informatik und Mathematik

Fields of Expertise

  • Information, Communication & Computing

Dieses zitieren