Projects per year
Abstract
For sets of n= 2 m points in general position in the plane we consider straightline 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 mth 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≤164n2O(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  4659 
Number of pages  14 
ISBN (Electronic)  9783031066788 
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 
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)  03029743 
ISSN (Electronic)  16113349 
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
 Computer Science(all)
Fields of Expertise
 Information, Communication & Computing
Projects
 1 Active

Doctoral Program: Discrete Mathematics
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., SavaHuss, E., Klinz, B., Heuberger, C., Grabner, P., Barroero, F., Cuno, J., Kreso, D., Berkes, I. & Kerber, M.
1/05/10 → 30/06/24
Project: Research project
Activities
 1 Talk at conference or symposium

Perfect Matchings with crossings
Rosna Paul (Speaker)
7 Jun 2022 → 9 Jun 2022Activity: Talk or presentation › Talk at conference or symposium › Science to science