Standard
Perfect Matchings with Crossings. / Aichholzer, Oswin; Fabila-Monroy, Ruy; Kindermann, Philipp; Parada, Irene; Paul, Rosna; Perz, Daniel; Schnider, Patrick; Vogtenhuber, Birgit.
Combinatorial Algorithms - 33rd International Workshop, IWOCA 2022, Proceedings. ed. / Cristina Bazgan; Henning Fernau. Springer, 2022. p. 46-59 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 13270 LNCS).
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
Aichholzer, O, Fabila-Monroy, R, Kindermann, P, Parada, I, Paul, R, Perz, D, Schnider, P & Vogtenhuber, B 2022,
Perfect Matchings with Crossings. in C Bazgan & H Fernau (eds),
Combinatorial Algorithms - 33rd International Workshop, IWOCA 2022, Proceedings. Springer, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13270 LNCS, pp. 46-59, 33rd International Workshop on Combinatorial Algorithms, IWOCA 2022, Trier, Germany,
07/06/2022.
https://doi.org/10.1007/978-3-031-06678-8_4APA
Aichholzer, O., Fabila-Monroy, R., Kindermann, P., Parada, I., Paul, R., Perz, D., Schnider, P., & Vogtenhuber, B. (2022).
Perfect Matchings with Crossings. In C. Bazgan, & H. Fernau (Eds.),
Combinatorial Algorithms - 33rd International Workshop, IWOCA 2022, Proceedings (pp. 46-59). Springer. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) Vol. 13270 LNCS
https://doi.org/10.1007/978-3-031-06678-8_4Vancouver
Aichholzer O, Fabila-Monroy R, Kindermann P, Parada I, Paul R, Perz D et al.
Perfect Matchings with Crossings. In Bazgan C, Fernau H, editors, Combinatorial Algorithms - 33rd International Workshop, IWOCA 2022, Proceedings. Springer. 2022. p. 46-59. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 13270 LNCS).
https://doi.org/10.1007/978-3-031-06678-8_4Author
Aichholzer, Oswin ; Fabila-Monroy, Ruy ; Kindermann, Philipp ; Parada, Irene ; Paul, Rosna ; Perz, Daniel ; Schnider, Patrick ; Vogtenhuber, Birgit. / Perfect Matchings with Crossings. Combinatorial Algorithms - 33rd International Workshop, IWOCA 2022, Proceedings. editor / Cristina Bazgan ; Henning Fernau. Springer, 2022. pp. 46-59 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 13270 LNCS).
Bibtex
@inproceedings{85f39bbb6772430e982c734d2589be90,
title = "Perfect Matchings with Crossings",
abstract = "For sets of n= 2 m points 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 Cm different plane perfect matchings, where Cm is the m-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-O(nn), any set of 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 fewer than 572n2 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, 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} 2022, Springer Nature Switzerland AG.; 33rd International Workshop on Combinatorial Algorithms, IWOCA 2022 ; Conference date: 07-06-2022 Through 09-06-2022",
year = "2022",
doi = "10.1007/978-3-031-06678-8_4",
language = "English",
isbn = "9783031066771",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer",
pages = "46--59",
editor = "Cristina Bazgan and Henning Fernau",
booktitle = "Combinatorial Algorithms - 33rd International Workshop, IWOCA 2022, Proceedings",
address = "Switzerland",
}
RIS
TY - GEN
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:
© 2022, Springer Nature Switzerland AG.
PY - 2022
Y1 - 2022
N2 - For sets of n= 2 m points 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 Cm different plane perfect matchings, where Cm is the m-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-O(nn), any set of 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 fewer than 572n2 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= 2 m points 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 Cm different plane perfect matchings, where Cm is the m-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-O(nn), any set of 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 fewer than 572n2 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 - Order types
KW - Perfect matchings
UR - http://www.scopus.com/inward/record.url?scp=85131928096&partnerID=8YFLogxK
U2 - 10.1007/978-3-031-06678-8_4
DO - 10.1007/978-3-031-06678-8_4
M3 - Article in proceedings
AN - SCOPUS:85131928096
SN - 9783031066771
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 46
EP - 59
BT - Combinatorial Algorithms - 33rd International Workshop, IWOCA 2022, Proceedings
A2 - Bazgan, Cristina
A2 - Fernau, Henning
PB - Springer
T2 - 33rd International Workshop on Combinatorial Algorithms, IWOCA 2022
Y2 - 7 June 2022 through 9 June 2022
ER -
