Perfect Matchings with Crossings
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Dokumenter
- Fulltext
Indsendt manuskript, 563 KB, PDF-dokument
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.
Originalsprog | Engelsk |
---|---|
Titel | Combinatorial Algorithms - 33rd International Workshop, IWOCA 2022, Proceedings |
Redaktører | Cristina Bazgan, Henning Fernau |
Forlag | Springer |
Publikationsdato | 2022 |
Sider | 46-59 |
ISBN (Trykt) | 9783031066771 |
DOI | |
Status | Udgivet - 2022 |
Begivenhed | 33rd International Workshop on Combinatorial Algorithms, IWOCA 2022 - Trier, Tyskland Varighed: 7 jun. 2022 → 9 jun. 2022 |
Konference
Konference | 33rd International Workshop on Combinatorial Algorithms, IWOCA 2022 |
---|---|
Land | Tyskland |
By | Trier |
Periode | 07/06/2022 → 09/06/2022 |
Navn | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Vol/bind | 13270 LNCS |
ISSN | 0302-9743 |
Bibliografisk note
Funding Information:
Keywords: Perfect matchings · Crossings · Combinatorial geometry · Order types Research on this work has been initiated at the 16th European Research Week on Geometric Graphs which was held from November 18 to 22, 2019, near Strobl (Austria). We thank all participants for the good atmosphere as well as for discussions on the topic. Further, we thank Clemens Huemer for bringing this problem to our attention in the course of a meeting of the H2020-MSCA-RISE project 73499 - CONNECT. O. A. and R. P. supported by FWF grant W1230. R. M. partially supported by CONA-CYT(Mexico) grant 253261. P. S. supported by ERC Grant ERC StG 716424-CASe. D. P., I. P., and B. V. supported by FWF Project I 3340-N35. Some results of this work have been presented at the “Computational Geometry: Young Researchers Forum” in 2021 [2].
Publisher Copyright:
© 2022, Springer Nature Switzerland AG.
Antal downloads er baseret på statistik fra Google Scholar og www.ku.dk
ID: 318812224