[{"publisher":"Springer Nature","page":"221-233","quality_controlled":"1","ec_funded":1,"title":"On compatible matchings","alternative_title":["LNCS"],"intvolume":"     12635","publication_status":"published","article_processing_charge":"No","date_created":"2021-03-28T22:01:41Z","department":[{"_id":"UlWa"},{"_id":"HeEd"},{"_id":"KrCh"}],"author":[{"first_name":"Oswin","last_name":"Aichholzer","full_name":"Aichholzer, Oswin"},{"id":"3207FDC6-F248-11E8-B48F-1D18A9856A87","last_name":"Arroyo Guevara","first_name":"Alan M","full_name":"Arroyo Guevara, Alan M","orcid":"0000-0003-2401-8670"},{"last_name":"Masárová","first_name":"Zuzana","full_name":"Masárová, Zuzana","orcid":"0000-0002-6660-1322","id":"45CFE238-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Parada, Irene","last_name":"Parada","first_name":"Irene"},{"full_name":"Perz, Daniel","last_name":"Perz","first_name":"Daniel"},{"last_name":"Pilz","first_name":"Alexander","full_name":"Pilz, Alexander"},{"first_name":"Josef","last_name":"Tkadlec","orcid":"0000-0002-1097-9684","full_name":"Tkadlec, Josef","id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Vogtenhuber, Birgit","last_name":"Vogtenhuber","first_name":"Birgit"}],"_id":"9296","scopus_import":"1","volume":12635,"acknowledgement":"A.A. funded by the Marie Skłodowska-Curie grant agreement No. 754411. Z.M. partially funded by Wittgenstein Prize, Austrian Science Fund (FWF), grant no. Z 342-N31. I.P., D.P., and B.V. partially supported by FWF within the collaborative DACH project Arrangements and Drawings as FWF project I 3340-N35. A.P. supported by a Schrödinger fellowship of the FWF: J-3847-N35. J.T. partially supported by ERC Start grant no. (279307: Graph Games), FWF grant no. P23499-N23 and S11407-N23 (RiSE).","abstract":[{"text":" 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   Ω(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   Θ(logn)  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.","lang":"eng"}],"doi":"10.1007/978-3-030-68211-8_18","arxiv":1,"day":"16","external_id":{"arxiv":["2101.03928"]},"date_updated":"2023-02-21T16:33:44Z","citation":{"mla":"Aichholzer, Oswin, et al. “On Compatible Matchings.” <i>15th International Conference on Algorithms and Computation</i>, vol. 12635, Springer Nature, 2021, pp. 221–33, doi:<a href=\"https://doi.org/10.1007/978-3-030-68211-8_18\">10.1007/978-3-030-68211-8_18</a>.","short":"O. Aichholzer, A.M. Arroyo Guevara, Z. Masárová, I. Parada, D. Perz, A. Pilz, J. Tkadlec, B. Vogtenhuber, in:, 15th International Conference on Algorithms and Computation, Springer Nature, 2021, pp. 221–233.","ista":"Aichholzer O, Arroyo Guevara AM, Masárová Z, Parada I, Perz D, Pilz A, Tkadlec J, Vogtenhuber B. 2021. On compatible matchings. 15th International Conference on Algorithms and Computation. WALCOM: Algorithms and Computation, LNCS, vol. 12635, 221–233.","ama":"Aichholzer O, Arroyo Guevara AM, Masárová Z, et al. On compatible matchings. In: <i>15th International Conference on Algorithms and Computation</i>. Vol 12635. Springer Nature; 2021:221-233. doi:<a href=\"https://doi.org/10.1007/978-3-030-68211-8_18\">10.1007/978-3-030-68211-8_18</a>","apa":"Aichholzer, O., Arroyo Guevara, A. M., Masárová, Z., Parada, I., Perz, D., Pilz, A., … Vogtenhuber, B. (2021). On compatible matchings. In <i>15th International Conference on Algorithms and Computation</i> (Vol. 12635, pp. 221–233). Yangon, Myanmar: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-68211-8_18\">https://doi.org/10.1007/978-3-030-68211-8_18</a>","ieee":"O. Aichholzer <i>et al.</i>, “On compatible matchings,” in <i>15th International Conference on Algorithms and Computation</i>, Yangon, Myanmar, 2021, vol. 12635, pp. 221–233.","chicago":"Aichholzer, Oswin, Alan M Arroyo Guevara, Zuzana Masárová, Irene Parada, Daniel Perz, Alexander Pilz, Josef Tkadlec, and Birgit Vogtenhuber. “On Compatible Matchings.” In <i>15th International Conference on Algorithms and Computation</i>, 12635:221–33. Springer Nature, 2021. <a href=\"https://doi.org/10.1007/978-3-030-68211-8_18\">https://doi.org/10.1007/978-3-030-68211-8_18</a>."},"year":"2021","conference":{"location":"Yangon, Myanmar","end_date":"2021-03-02","start_date":"2021-02-28","name":"WALCOM: Algorithms and Computation"},"language":[{"iso":"eng"}],"month":"02","oa_version":"Preprint","project":[{"name":"ISTplus - Postdoctoral Fellowships","grant_number":"754411","call_identifier":"H2020","_id":"260C2330-B435-11E9-9278-68D0E5697425"},{"grant_number":"Z00342","name":"The Wittgenstein Prize","call_identifier":"FWF","_id":"268116B8-B435-11E9-9278-68D0E5697425"},{"name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"},{"call_identifier":"FWF","_id":"2584A770-B435-11E9-9278-68D0E5697425","name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23"},{"grant_number":"S11407","name":"Game Theory","call_identifier":"FWF","_id":"25863FF4-B435-11E9-9278-68D0E5697425"}],"publication":"15th International Conference on Algorithms and Computation","status":"public","related_material":{"record":[{"id":"11938","relation":"later_version","status":"public"}]},"user_id":"D865714E-FA4E-11E9-B85B-F5C5E5697425","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2101.03928"}],"oa":1,"publication_identifier":{"eissn":["16113349"],"issn":["03029743"],"isbn":["9783030682101"]},"date_published":"2021-02-16T00:00:00Z","type":"conference"}]