Perfect Matchings with Crossings

Research output: Contribution to journal › Journal article › Research › peer-review

Standard

Perfect Matchings with Crossings. / Aichholzer, Oswin; Fabila-Monroy, Ruy; Kindermann, Philipp; Parada, Irene; Paul, Rosna; Perz, Daniel; Schnider, Patrick; Vogtenhuber, Birgit.

In: Algorithmica, Vol. 86, 2024, p. 697–716.

Research output: Contribution to journal › Journal article › Research › peer-review

Harvard

Aichholzer, O, Fabila-Monroy, R, Kindermann, P, Parada, I, Paul, R, Perz, D, Schnider, P & Vogtenhuber, B 2024, 'Perfect Matchings with Crossings', Algorithmica, vol. 86, pp. 697–716. https://doi.org/10.1007/s00453-023-01147-7

APA

Aichholzer, O., Fabila-Monroy, R., Kindermann, P., Parada, I., Paul, R., Perz, D., Schnider, P., & Vogtenhuber, B. (2024). Perfect Matchings with Crossings. Algorithmica, 86, 697–716. https://doi.org/10.1007/s00453-023-01147-7

Vancouver

Aichholzer O, Fabila-Monroy R, Kindermann P, Parada I, Paul R, Perz D et al. Perfect Matchings with Crossings. Algorithmica. 2024;86:697–716. https://doi.org/10.1007/s00453-023-01147-7

Author

Aichholzer, Oswin ; Fabila-Monroy, Ruy ; Kindermann, Philipp ; Parada, Irene ; Paul, Rosna ; Perz, Daniel ; Schnider, Patrick ; Vogtenhuber, Birgit. / Perfect Matchings with Crossings. In: Algorithmica. 2024 ; Vol. 86. pp. 697–716.

Bibtex

@article{85138a5da1234c3c96a6ab18ea40bab9,

title = "Perfect Matchings with Crossings",

abstract = "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.",

keywords = "Combinatorial geometry, Crossings, Geometric graphs, Order types, Perfect matchings",

author = "Oswin Aichholzer and Ruy Fabila-Monroy and Philipp Kindermann and Irene Parada and Rosna Paul and Daniel Perz and Patrick Schnider and Birgit Vogtenhuber",

note = "Publisher Copyright: {\textcopyright} 2023, The Author(s).",

year = "2024",

doi = "10.1007/s00453-023-01147-7",

language = "English",

volume = "86",

pages = "697–716",

journal = "Algorithmica",

issn = "0178-4617",

publisher = "Springer",

}

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

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

Department of Mathematical Sciences