Geodesic
On Compatible Matchings
Journal of Graph Algorithms and Applications, Special Issue on Selected Papers from the 15th International Conference and Workshops on Algorithms and Computation, WALCOM 2021 , Tome 26 (2022) no. 2, pp. 225-240.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

A matching is compatible to two or more labeled point sets of size $n$ with labels $\{1,\dots,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 $\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.
DOI : 10.7155/jgaa.00591
Keywords: compatible graphs, crossing-free matchings, geometric graphs 
@article{JGAA_2022_26_2_a2,
     author = {Oswin Aichholzer and Alan Arroyo and Zuzana Mas\'arov\'a and Irene Parada and Daniel Perz and Alexander Pilz and Josef Tkadlec and Birgit Vogtenhuber},
     title = {On {Compatible} {Matchings}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {225--240},
     publisher = {mathdoc},
     volume = {26},
     number = {2},
     year = {2022},
     doi = {10.7155/jgaa.00591},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00591/}
}
TY  - JOUR
AU  - Oswin Aichholzer
AU  - Alan Arroyo
AU  - Zuzana Masárová
AU  - Irene Parada
AU  - Daniel Perz
AU  - Alexander Pilz
AU  - Josef Tkadlec
AU  - Birgit Vogtenhuber
TI  - On Compatible Matchings
JO  - Journal of Graph Algorithms and Applications
PY  - 2022
SP  - 225
EP  - 240
VL  - 26
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00591/
DO  - 10.7155/jgaa.00591
LA  - en
ID  - JGAA_2022_26_2_a2
ER  - 
%0 Journal Article
%A Oswin Aichholzer
%A Alan Arroyo
%A Zuzana Masárová
%A Irene Parada
%A Daniel Perz
%A Alexander Pilz
%A Josef Tkadlec
%A Birgit Vogtenhuber
%T On Compatible Matchings
%J Journal of Graph Algorithms and Applications
%D 2022
%P 225-240
%V 26
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00591/
%R 10.7155/jgaa.00591
%G en
%F JGAA_2022_26_2_a2
Oswin Aichholzer; Alan Arroyo; Zuzana Masárová; Irene Parada; Daniel Perz; Alexander Pilz; Josef Tkadlec; Birgit Vogtenhuber. On Compatible Matchings. Journal of Graph Algorithms and Applications, 
							Special Issue on Selected Papers from the 15th International Conference and  Workshops on Algorithms and Computation, WALCOM 2021
					, Tome 26 (2022) no. 2, pp. 225-240. doi : 10.7155/jgaa.00591. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00591/

Cité par Sources :