article published yes Oswin Aichholzer author Alan M Arroyo Guevara author 3207FDC6-F248-11E8-B48F-1D18A9856A870000-0003-2401-8670 Zuzana Masárová author 45CFE238-F248-11E8-B48F-1D18A9856A870000-0002-6660-1322 Irene Parada author Daniel Perz author Alexander Pilz author Josef Tkadlec author 3F24CCC8-F248-11E8-B48F-1D18A9856A870000-0002-1097-9684 Birgit Vogtenhuber author UlWa department HeEd department KrCh department ISTplus - Postdoctoral Fellowships project Mathematics, Computer Science project Quantitative Graph Games: Theory and Applications project Modern Graph Algorithmic Techniques in Formal Verification project Game Theory project 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. https://research-explorer.ista.ac.at/download/11938/11940/2022_JourGraphAlgorithmsApplic_Aichholzer.pdf application/pdfno https://creativecommons.org/licenses/by/4.0/ Brown University2022 eng 1526-1719 2101.0392810.7155/jgaa.00591 262225-240 https://research-explorer.ista.ac.at/record/9296 Aichholzer, Oswin, et al. “On Compatible Matchings.” <i>Journal of Graph Algorithms and Applications</i>, vol. 26, no. 2, Brown University, 2022, pp. 225–40, doi:<a href="https://doi.org/10.7155/jgaa.00591">10.7155/jgaa.00591</a>. Aichholzer, Oswin, Alan M Arroyo Guevara, Zuzana Masárová, Irene Parada, Daniel Perz, Alexander Pilz, Josef Tkadlec, and Birgit Vogtenhuber. “On Compatible Matchings.” <i>Journal of Graph Algorithms and Applications</i>. Brown University, 2022. <a href="https://doi.org/10.7155/jgaa.00591">https://doi.org/10.7155/jgaa.00591</a>. O. Aichholzer <i>et al.</i>, “On compatible matchings,” <i>Journal of Graph Algorithms and Applications</i>, vol. 26, no. 2. Brown University, pp. 225–240, 2022. Aichholzer, O., Arroyo Guevara, A. M., Masárová, Z., Parada, I., Perz, D., Pilz, A., … Vogtenhuber, B. (2022). On compatible matchings. <i>Journal of Graph Algorithms and Applications</i>. Brown University. <a href="https://doi.org/10.7155/jgaa.00591">https://doi.org/10.7155/jgaa.00591</a> Aichholzer O, Arroyo Guevara AM, Masárová Z, Parada I, Perz D, Pilz A, Tkadlec J, Vogtenhuber B. 2022. On compatible matchings. Journal of Graph Algorithms and Applications. 26(2), 225–240. 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> O. Aichholzer, A.M. Arroyo Guevara, Z. Masárová, I. Parada, D. Perz, A. Pilz, J. Tkadlec, B. Vogtenhuber, Journal of Graph Algorithms and Applications 26 (2022) 225–240. 119382022-08-21T22:01:56Z2026-04-16T09:18:20Z