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 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.
Originalsprache | englisch |
---|---|
Seiten (von - bis) | 225-240 |
Seitenumfang | 16 |
Fachzeitschrift | Journal of Graph Algorithms and Applications |
Jahrgang | 26 |
Ausgabenummer | 2 |
DOIs | |
Publikationsstatus | Veröffentlicht - 2022 |
ASJC Scopus subject areas
- Theoretische Informatik
- Allgemeine Computerwissenschaft
- Angewandte Informatik
- Geometrie und Topologie
- Theoretische Informatik und Mathematik
Fields of Expertise
- Information, Communication & Computing