On Compatible Matchings

Oswin Aichholzer; Alan Arroyo; Zuzana Masárová; Irene Parada; Daniel Perz; Alexander Pilz; Josef Tkadlec; Birgit Vogtenhuber

doi:10.1007/978-3-030-68211-8_18

On Compatible Matchings

Oswin Aichholzer
, Alan Arroyo
, Zuzana Masárová
, Irene Parada
, Daniel Perz
, Alexander Pilz
, Josef Tkadlec
, Birgit Vogtenhuber

Institute of Software Engineering and Artificial Intelligence (7160)

Research output: Chapter in Book/Report/Conference proceeding › Conference paper › peer-review

Abstract

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 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 Ω(n ¹ ^/ ^ℓ). 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(n ² ^/ ⁽ ^ℓ ⁺ ¹ ⁾) edges. Finally, we show that Θ(log n) 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.

Original language	English
Title of host publication	WALCOM
Subtitle of host publication	Algorithms and Computation - 15th International Conference and Workshops, WALCOM 2021, Proceedings
Editors	Ryuhei Uehara, Seok-Hee Hong, Subhas C. Nandy
Pages	221-233
Number of pages	13
DOIs	https://doi.org/10.1007/978-3-030-68211-8_18
Publication status	Published - 2021

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	12635 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Keywords

Compatible graphs
Crossing-free matchings
Geometric graphs

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Fields of Expertise

Information, Communication & Computing

Access to Document

10.1007/978-3-030-68211-8_18

Cite this

Aichholzer, O., Arroyo, A., Masárová, Z., Parada, I., Perz, D., Pilz, A., Tkadlec, J., & Vogtenhuber, B. (2021). On Compatible Matchings. In R. Uehara, S.-H. Hong, & S. C. Nandy (Eds.), WALCOM: Algorithms and Computation - 15th International Conference and Workshops, WALCOM 2021, Proceedings (pp. 221-233). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12635 LNCS). https://doi.org/10.1007/978-3-030-68211-8_18

On Compatible Matchings. / Aichholzer, Oswin; Arroyo, Alan; Masárová, Zuzana et al.
WALCOM: Algorithms and Computation - 15th International Conference and Workshops, WALCOM 2021, Proceedings. ed. / Ryuhei Uehara; Seok-Hee Hong; Subhas C. Nandy. 2021. p. 221-233 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12635 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference paper › peer-review

Aichholzer, O, Arroyo, A, Masárová, Z, Parada, I, Perz, D, Pilz, A, Tkadlec, J & Vogtenhuber, B 2021, On Compatible Matchings. in R Uehara, S-H Hong & SC Nandy (eds), WALCOM: Algorithms and Computation - 15th International Conference and Workshops, WALCOM 2021, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12635 LNCS, pp. 221-233. https://doi.org/10.1007/978-3-030-68211-8_18

Aichholzer O, Arroyo A, Masárová Z, Parada I, Perz D, Pilz A et al. On Compatible Matchings. In Uehara R, Hong SH, Nandy SC, editors, WALCOM: Algorithms and Computation - 15th International Conference and Workshops, WALCOM 2021, Proceedings. 2021. p. 221-233. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-68211-8_18

Aichholzer, Oswin ; Arroyo, Alan ; Masárová, Zuzana et al. / On Compatible Matchings. WALCOM: Algorithms and Computation - 15th International Conference and Workshops, WALCOM 2021, Proceedings. editor / Ryuhei Uehara ; Seok-Hee Hong ; Subhas C. Nandy. 2021. pp. 221-233 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{6691adc10bdf47028e012ba6e1891183,

title = "On Compatible Matchings",

abstract = "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 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 Ω(n 1 / ℓ). 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(n 2 / ( ℓ + 1 )) edges. Finally, we show that Θ(log n) 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. ",

keywords = "Compatible graphs, Crossing-free matchings, Geometric graphs",

author = "Oswin Aichholzer and Alan Arroyo and Zuzana Mas{\'a}rov{\'a} and Irene Parada and Daniel Perz and Alexander Pilz and Josef Tkadlec and Birgit Vogtenhuber",

year = "2021",

doi = "10.1007/978-3-030-68211-8\_18",

language = "English",

isbn = "9783030682101",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "221--233",

editor = "Ryuhei Uehara and Seok-Hee Hong and Nandy, \{Subhas C.\}",

booktitle = "WALCOM",

}

TY - GEN

T1 - On Compatible Matchings

AU - Aichholzer, Oswin

AU - Arroyo, Alan

AU - Masárová, Zuzana

AU - Parada, Irene

AU - Perz, Daniel

AU - Pilz, Alexander

AU - Tkadlec, Josef

AU - Vogtenhuber, Birgit

PY - 2021

Y1 - 2021

N2 - 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 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 Ω(n 1 / ℓ). 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(n 2 / ( ℓ + 1 )) edges. Finally, we show that Θ(log n) 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.

AB - 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 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 Ω(n 1 / ℓ). 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(n 2 / ( ℓ + 1 )) edges. Finally, we show that Θ(log n) 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.

KW - Compatible graphs

KW - Crossing-free matchings

KW - Geometric graphs

UR - https://www.scopus.com/pages/publications/85102726688

UR - http://arxiv.org/abs/2101.03928v2

U2 - 10.1007/978-3-030-68211-8_18

DO - 10.1007/978-3-030-68211-8_18

M3 - Conference paper

SN - 9783030682101

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 221

EP - 233

BT - WALCOM

A2 - Uehara, Ryuhei

A2 - Hong, Seok-Hee

A2 - Nandy, Subhas C.

ER -

On Compatible Matchings

Abstract

Publication series

Keywords

ASJC Scopus subject areas

Fields of Expertise

Access to Document

Other files and links