Home  Issues  About JGAA  Instructions for Authors 
Special Issue on Selected Papers from the 15th International Conference and Workshops on Algorithms and Computation, WALCOM 2021
DOI: 10.7155/jgaa.00591
On Compatible Matchings
Oswin Aichholzer,
Alan Arroyo,
Zuzana Masárová,
Irene Parada,
Daniel Perz,
Alexander Pilz,
Josef Tkadlec, and
Birgit Vogtenhuber
Vol. 26, no. 2, pp. 225240, 2022. Regular paper.
Abstract A matching is compatible to two or more labeled point sets of size $n$ with labels $\{1,\dots,n\}$ if its straightline drawing on each of these point sets is crossingfree.
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 $\lfloor \sqrt {2n+1} 1\rfloor$ edges.
More generally, for any $\ell$ labeled point sets we construct compatible matchings of size $\Omega(n^{1/\ell})$.
As a corresponding upper bound, we use probabilistic arguments to show that for any $\ell$ given sets of $n$ points there exists a labeling of each set such that the largest compatible matching has $O(n^{2/(\ell+1)})$ edges.
Finally, we show that $\Theta(\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.
This work is licensed under the terms of the CCBY license.

Submitted: April 2021.
Reviewed: August 2021.
Revised: October 2021.
Accepted: December 2021.
Final: January 2022.
Published: June 2022.

Journal Supporters
