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

^*Corresponding author for this work

Institute of Software Engineering and Artificial Intelligence (7160)

Research output: Chapter in Book/Report/Conference proceeding › Conference paper › peer-review

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.

Original language	English
Title of host publication	Combinatorial Algorithms
Subtitle of host publication	33rd International Workshop, IWOCA 2022, Trier, Germany, June 7–9, 2022, Proceedings
Editors	Cristina Bazgan, Henning Fernau
Place of Publication	Cham
Publisher	Springer
Pages	46-59
Number of pages	14
ISBN (Electronic)	978-3-031-06678-8
ISBN (Print)	978-3-031-06677-1
DOIs	https://doi.org/10.1007/978-3-031-06678-8_4
Publication status	Published - 2022
Event	33rd International Workshop on Combinatorial Algorithms: IWOCA 2022 - Trier, Germany Duration: 7 Jun 2022 → 9 Jun 2022

Publication series

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

Conference

Conference	33rd International Workshop on Combinatorial Algorithms
Country/Territory	Germany
City	Trier
Period	7/06/22 → 9/06/22

Keywords

Perfect matchings
crossings
Combinatorial geometry
Order types
Crossings

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Fields of Expertise

Information, Communication & Computing

Access to Document

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

Cite this

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, Trier, Germany, June 7–9, 2022, Proceedings (pp. 46-59). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 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. ed. / Cristina Bazgan; Henning Fernau. Cham: 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 › Conference paper › peer-review

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, Trier, Germany, June 7–9, 2022, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13270 LNCS, Springer, Cham, pp. 46-59, 33rd International Workshop on Combinatorial Algorithms, Trier, Germany, 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, editors, Combinatorial Algorithms : 33rd International Workshop, IWOCA 2022, Trier, Germany, June 7–9, 2022, Proceedings. Cham: Springer. 2022. p. 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. editor / Cristina Bazgan ; Henning Fernau. Cham : Springer, 2022. pp. 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",

address = "United States",

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 - https://www.scopus.com/pages/publications/85131928096

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

Publication series

Conference

Keywords

ASJC Scopus subject areas

Fields of Expertise

Access to Document

Other files and links

Doctoral Program: Discrete Mathematics