Perfect Matchings with Crossings
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Documents
- Fulltext
Submitted manuscript, 563 KB, PDF document
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.
Original language | English |
---|---|
Title of host publication | Combinatorial Algorithms - 33rd International Workshop, IWOCA 2022, Proceedings |
Editors | Cristina Bazgan, Henning Fernau |
Publisher | Springer |
Publication date | 2022 |
Pages | 46-59 |
ISBN (Print) | 9783031066771 |
DOIs | |
Publication status | Published - 2022 |
Event | 33rd International Workshop on Combinatorial Algorithms, IWOCA 2022 - Trier, Germany Duration: 7 Jun 2022 → 9 Jun 2022 |
Conference
Conference | 33rd International Workshop on Combinatorial Algorithms, IWOCA 2022 |
---|---|
Land | Germany |
By | Trier |
Periode | 07/06/2022 → 09/06/2022 |
Series | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Volume | 13270 LNCS |
ISSN | 0302-9743 |
Bibliographical note
Publisher Copyright:
© 2022, Springer Nature Switzerland AG.
- Combinatorial geometry, Crossings, Order types, Perfect matchings
Research areas
Number of downloads are based on statistics from Google Scholar and www.ku.dk
ID: 318812224