Perfect Matchings with Crossings
Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt
Dokumenter
- Fulltext
Forlagets udgivne version, 622 KB, PDF-dokument
For sets of n points, n even, 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 Cn/2 different plane perfect matchings, where Cn/2 is the n/2-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-3532nn+122564n , any set with 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 at most 572n2-n4 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 |
---|---|
Tidsskrift | Algorithmica |
Vol/bind | 86 |
Sider (fra-til) | 697–716 |
ISSN | 0178-4617 |
DOI | |
Status | Udgivet - 2024 |
Bibliografisk note
Funding Information:
Research on this work was 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 734922 - CONNECT. O. A. and R. P. supported by FWF Grant W1230. P. S. supported by ERC Grant ERC StG 716424-CASe. D. P., I. P., and B. V. supported by FWF Project I 3340-N35. I. P. supported by the Independent Research Fund Denmark Grant 2020-2023 (9131-00044B) “Dynamic Network Analysis” and by the Margarita Salas Fellowship funded by the Ministry of Universities of Spain and the European Union (NextGenerationEU).
Funding Information:
Open access funding provided by Austrian Science Fund (FWF). Nothing other than that in Acknowledgements.
Publisher Copyright:
© 2023, The Author(s).
ID: 360263031