Perfect Matchings with Crossings
Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt
Standard
Perfect Matchings with Crossings. / Aichholzer, Oswin; Fabila-Monroy, Ruy; Kindermann, Philipp; Parada, Irene; Paul, Rosna; Perz, Daniel; Schnider, Patrick; Vogtenhuber, Birgit.
I: Algorithmica, Bind 86, 2024, s. 697–716.Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - JOUR
T1 - Perfect Matchings with Crossings
AU - Aichholzer, Oswin
AU - Fabila-Monroy, Ruy
AU - Kindermann, Philipp
AU - Parada, Irene
AU - Paul, Rosna
AU - Perz, Daniel
AU - Schnider, Patrick
AU - Vogtenhuber, Birgit
N1 - Publisher Copyright: © 2023, The Author(s).
PY - 2024
Y1 - 2024
N2 - For sets of n points, n even, in general position in the plane, we consider straight-line drawings of perfect matchings on them. It is well known that such sets admit at least Cn/2 different plane perfect matchings, where Cn/2 is the n/2-th Catalan number. Generalizing this result we are interested in the number of drawings of perfect matchings which have k crossings. We show the following results. (1) For every k≤164n2-3532nn+122564n , any set with n points, n sufficiently large, admits a perfect matching with exactly k crossings. (2) There exist sets of n points where every perfect matching has at most 572n2-n4 crossings. (3) The number of perfect matchings with at most k crossings is superexponential in n if k is superlinear in n. (4) Point sets in convex position minimize the number of perfect matchings with at most k crossings for k= 0 , 1 , 2 , and maximize the number of perfect matchings with (n/22) crossings and with (n/22)-1 crossings.
AB - For sets of n points, n even, in general position in the plane, we consider straight-line drawings of perfect matchings on them. It is well known that such sets admit at least Cn/2 different plane perfect matchings, where Cn/2 is the n/2-th Catalan number. Generalizing this result we are interested in the number of drawings of perfect matchings which have k crossings. We show the following results. (1) For every k≤164n2-3532nn+122564n , any set with n points, n sufficiently large, admits a perfect matching with exactly k crossings. (2) There exist sets of n points where every perfect matching has at most 572n2-n4 crossings. (3) The number of perfect matchings with at most k crossings is superexponential in n if k is superlinear in n. (4) Point sets in convex position minimize the number of perfect matchings with at most k crossings for k= 0 , 1 , 2 , and maximize the number of perfect matchings with (n/22) crossings and with (n/22)-1 crossings.
KW - Combinatorial geometry
KW - Crossings
KW - Geometric graphs
KW - Order types
KW - Perfect matchings
U2 - 10.1007/s00453-023-01147-7
DO - 10.1007/s00453-023-01147-7
M3 - Journal article
C2 - 38481794
AN - SCOPUS:85165010912
VL - 86
SP - 697
EP - 716
JO - Algorithmica
JF - Algorithmica
SN - 0178-4617
ER -
ID: 360263031