On compatible matchings Aichholzer, Oswin Arroyo Guevara, Alan M ; https://orcid.org/0000-0003-2401-8670 Masárová, Zuzana ; https://orcid.org/0000-0002-6660-1322 Parada, Irene Perz, Daniel Pilz, Alexander Tkadlec, Josef ; https://orcid.org/0000-0002-1097-9684 Vogtenhuber, Birgit ddc:000 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. Brown University 2022 info:eu-repo/semantics/article doc-type:Article Article http://purl.org/coar/resource_type/c_2df8fbb1 https://research-explorer.ista.ac.at/record/11938 https://research-explorer.ista.ac.at/download/11938/11940 Aichholzer O, Arroyo Guevara AM, Masárová Z, et al. On compatible matchings. <i>Journal of Graph Algorithms and Applications</i>. 2022;26(2):225-240. doi:<a href="https://doi.org/10.7155/jgaa.00591">10.7155/jgaa.00591</a> eng info:eu-repo/semantics/altIdentifier/doi/10.7155/jgaa.00591 info:eu-repo/semantics/altIdentifier/issn/1526-1719 info:eu-repo/semantics/altIdentifier/arxiv/2101.03928 info:eu-repo/semantics/openAccess