Perfect Matchings with Crossings

Oswin Aichholzer; Ruy Fabila-Monroy; Philipp Kindermann; Irene Parada; Rosna Paul; Daniel Perz; Patrick Schnider; Birgit Vogtenhuber

doi:10.1007/978-3-031-06678-8_4

Perfect Matchings with Crossings

Oswin Aichholzer, Ruy Fabila-Monroy, Philipp Kindermann, Irene Parada, Rosna Paul^*, Daniel Perz, Patrick Schnider, Birgit Vogtenhuber

^*Korrespondierende/r Autor/-in für diese Arbeit

Institut für Softwaretechnologie (7160)

Publikation: Beitrag in Buch/Bericht/Konferenzband › Beitrag in einem Konferenzband › Begutachtung

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 C _m different plane perfect matchings, where C _m 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.

Originalsprache	englisch
Titel	Combinatorial Algorithms
Untertitel	33rd International Workshop, IWOCA 2022, Trier, Germany, June 7–9, 2022, Proceedings
Redakteure/-innen	Cristina Bazgan, Henning Fernau
Erscheinungsort	Cham
Herausgeber (Verlag)	Springer
Seiten	46-59
Seitenumfang	14
ISBN (elektronisch)	978-3-031-06678-8
ISBN (Print)	978-3-031-06677-1
DOIs	https://doi.org/10.1007/978-3-031-06678-8_4
Publikationsstatus	Veröffentlicht - 2022
Veranstaltung	33rd International Workshop on Combinatorial Algorithms: IWOCA 2022 - Trier, Deutschland Dauer: 7 Juni 2022 → 9 Juni 2022

Publikationsreihe

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Band	13270 LNCS
ISSN (Print)	0302-9743
ISSN (elektronisch)	1611-3349

Konferenz

Konferenz	33rd International Workshop on Combinatorial Algorithms
Land/Gebiet	Deutschland
Ort	Trier
Zeitraum	7/06/22 → 9/06/22

ASJC Scopus subject areas

Theoretische Informatik
Allgemeine Computerwissenschaft

Fields of Expertise

Information, Communication & Computing

Zugriff auf Dokument

10.1007/978-3-031-06678-8_4

Andere Dateien und Links

Verknüpfung zur Publikation in Scopus

DK Diskrete Mathematik
Ebner, O., Lehner, F., Greinecker, F., Burkard, R., Wallner, J., Elsholtz, C., Woess, W., Raseta, M., Bazarova, A., Krenn, D., Lehner, F., Kang, M., Tichy, R., Sava-Huss, E., Klinz, B., Heuberger, C., Grabner, P., Barroero, F., Cuno, J., Kreso, D., Berkes, I. & Kerber, M.
1/05/10 → 30/06/24
Projekt: Forschungsprojekt

Perfect Matchings with crossings
Rosna Paul (Redner/in)
7 Juni 2022 → 9 Juni 2022
Aktivität: Vortrag oder Präsentation › Vortrag bei Konferenz oder Fachtagung › Science to science

Dieses zitieren

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 (Hrsg.), Combinatorial Algorithms : 33rd International Workshop, IWOCA 2022, Trier, Germany, June 7–9, 2022, Proceedings (S. 46-59). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Band 13270 LNCS). Springer. https://doi.org/10.1007/978-3-031-06678-8_4

Perfect Matchings with Crossings. / Aichholzer, Oswin; Fabila-Monroy, Ruy; Kindermann, Philipp et al.
Combinatorial Algorithms : 33rd International Workshop, IWOCA 2022, Trier, Germany, June 7–9, 2022, Proceedings. Hrsg. / Cristina Bazgan; Henning Fernau. Cham: Springer, 2022. S. 46-59 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Band 13270 LNCS).

Publikation: Beitrag in Buch/Bericht/Konferenzband › Beitrag in einem Konferenzband › Begutachtung

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 (Hrsg.), Combinatorial Algorithms : 33rd International Workshop, IWOCA 2022, Trier, Germany, June 7–9, 2022, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Bd. 13270 LNCS, Springer, Cham, S. 46-59, 33rd International Workshop on Combinatorial Algorithms, Trier, Deutschland, 7/06/22. https://doi.org/10.1007/978-3-031-06678-8_4

Aichholzer O, Fabila-Monroy R, Kindermann P, Parada I, Paul R, Perz D et al. Perfect Matchings with Crossings. in Bazgan C, Fernau H, Hrsg., Combinatorial Algorithms : 33rd International Workshop, IWOCA 2022, Trier, Germany, June 7–9, 2022, Proceedings. Cham: Springer. 2022. S. 46-59. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-06678-8_4

Aichholzer, Oswin ; Fabila-Monroy, Ruy ; Kindermann, Philipp et al. / Perfect Matchings with Crossings. Combinatorial Algorithms : 33rd International Workshop, IWOCA 2022, Trier, Germany, June 7–9, 2022, Proceedings. Hrsg. / Cristina Bazgan ; Henning Fernau. Cham : Springer, 2022. S. 46-59 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{65d72f7a5d48490998875de23e981f1a,

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 C m different plane perfect matchings, where C m 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 = "Perfect matchings, crossings, Combinatorial geometry, Order types, Crossings",

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",

year = "2022",

doi = "10.1007/978-3-031-06678-8_4",

language = "English",

isbn = "978-3-031-06677-1",

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",

note = "33rd International Workshop on Combinatorial Algorithms : IWOCA 2022 ; Conference date: 07-06-2022 Through 09-06-2022",

}

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

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 C m different plane perfect matchings, where C m 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 C m different plane perfect matchings, where C m 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 - Perfect matchings

KW - crossings

KW - Combinatorial geometry

KW - Order types

KW - Crossings

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 - Conference paper

SN - 978-3-031-06677-1

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

A2 - Bazgan, Cristina

A2 - Fernau, Henning

PB - Springer

CY - Cham

T2 - 33rd International Workshop on Combinatorial Algorithms

Y2 - 7 June 2022 through 9 June 2022

ER -

Perfect Matchings with Crossings

Abstract

Publikationsreihe

Konferenz

ASJC Scopus subject areas

Fields of Expertise

Zugriff auf Dokument

Andere Dateien und Links

Fingerprint

Projekte

DK Diskrete Mathematik

Aktivitäten

Perfect Matchings with crossings

Dieses zitieren