{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T09:31:25Z","timestamp":1773912685047,"version":"3.50.1"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2023,7,18]],"date-time":"2023-07-18T00:00:00Z","timestamp":1689638400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,7,18]],"date-time":"2023-07-18T00:00:00Z","timestamp":1689638400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Austrian Science Fund"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2024,3]]},"abstract":"Abstract<\/jats:title>\n \n For sets of\n n<\/jats:italic>\n points,\n n<\/jats:italic>\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\n \n \n $$C_{n\/2}$$<\/jats:tex-math>\n \n \n C<\/mml:mi>\n \n n<\/mml:mi>\n \/<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msub>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n different plane perfect matchings, where\n \n \n $$C_{n\/2}$$<\/jats:tex-math>\n \n \n C<\/mml:mi>\n \n n<\/mml:mi>\n \/<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msub>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n is the\n n<\/jats:italic>\n \/2-th Catalan number. Generalizing this result we are interested in the number of drawings of perfect matchings which have\n k<\/jats:italic>\n crossings. We show the following results. (1)\u00a0For every\n \n \n $$k\\le \\frac{1}{64}n^2-\\frac{35}{32}n\\sqrt{n}+\\frac{1225}{64}n$$<\/jats:tex-math>\n \n \n k<\/mml:mi>\n \u2264<\/mml:mo>\n \n 1<\/mml:mn>\n 64<\/mml:mn>\n <\/mml:mfrac>\n \n n<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n -<\/mml:mo>\n \n 35<\/mml:mn>\n 32<\/mml:mn>\n <\/mml:mfrac>\n n<\/mml:mi>\n \n n<\/mml:mi>\n <\/mml:msqrt>\n +<\/mml:mo>\n \n 1225<\/mml:mn>\n 64<\/mml:mn>\n <\/mml:mfrac>\n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , any set with\n n<\/jats:italic>\n points,\n n<\/jats:italic>\n sufficiently large, admits a perfect matching with exactly\n k<\/jats:italic>\n crossings. (2)\u00a0There exist sets of\u00a0\n n<\/jats:italic>\n points where every perfect matching has at most\n \n \n $$\\frac{5}{72}n^2-\\frac{n}{4}$$<\/jats:tex-math>\n \n \n \n 5<\/mml:mn>\n 72<\/mml:mn>\n <\/mml:mfrac>\n \n n<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n -<\/mml:mo>\n \n n<\/mml:mi>\n 4<\/mml:mn>\n <\/mml:mfrac>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n crossings. (3)\u00a0The number of perfect matchings with at most\n k<\/jats:italic>\n crossings is superexponential in\n n<\/jats:italic>\n if\n k<\/jats:italic>\n is superlinear in\n n<\/jats:italic>\n . (4)\u00a0Point sets in convex position minimize the number of perfect matchings with at most\n k<\/jats:italic>\n crossings for\n \n \n $$k=0,1,2$$<\/jats:tex-math>\n \n \n k<\/mml:mi>\n =<\/mml:mo>\n 0<\/mml:mn>\n ,<\/mml:mo>\n 1<\/mml:mn>\n ,<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , and maximize the number of perfect matchings with\n \n \n $$\\left( {\\begin{array}{c}n\/2\\\\ 2\\end{array}}\\right) $$<\/jats:tex-math>\n \n \n \n \n \n \n \n n<\/mml:mi>\n \/<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:mtd>\n <\/mml:mtr>\n \n \n \n \n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:mtd>\n <\/mml:mtr>\n <\/mml:mtable>\n <\/mml:mrow>\n <\/mml:mfenced>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n crossings and with\n \n \n $${\\left( {\\begin{array}{c}n\/2\\\\ 2\\end{array}}\\right) }\\!-\\!1$$<\/jats:tex-math>\n \n \n \n \n \n \n \n \n n<\/mml:mi>\n \/<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:mtd>\n <\/mml:mtr>\n \n \n \n \n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:mtd>\n <\/mml:mtr>\n <\/mml:mtable>\n <\/mml:mrow>\n <\/mml:mfenced>\n \n -<\/mml:mo>\n \n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n crossings.\n <\/jats:p>","DOI":"10.1007\/s00453-023-01147-7","type":"journal-article","created":{"date-parts":[[2023,7,18]],"date-time":"2023-07-18T01:01:43Z","timestamp":1689642103000},"page":"697-716","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Perfect Matchings with Crossings"],"prefix":"10.1007","volume":"86","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2364-0583","authenticated-orcid":false,"given":"Oswin","family":"Aichholzer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2517-0298","authenticated-orcid":false,"given":"Ruy","family":"Fabila-Monroy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5764-7719","authenticated-orcid":false,"given":"Philipp","family":"Kindermann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3147-0083","authenticated-orcid":false,"given":"Irene","family":"Parada","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2458-6427","authenticated-orcid":false,"given":"Rosna","family":"Paul","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6557-2355","authenticated-orcid":false,"given":"Daniel","family":"Perz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2172-9285","authenticated-orcid":false,"given":"Patrick","family":"Schnider","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7166-4467","authenticated-orcid":false,"given":"Birgit","family":"Vogtenhuber","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,7,18]]},"reference":[{"key":"1147_CR1","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1007\/978-3-031-06678-8_4","volume-title":"Combinatorial Algorithms","author":"O Aichholzer","year":"2022","unstructured":"Aichholzer, O., Fabila-Monroy, R., Kindermann, P., Parada, I., Paul, R., Perz, D., Schnider, P., Vogtenhuber, B.: Perfect matchings with crossings. In: Bazgan, C., Fernau, H. (eds.) Combinatorial Algorithms, pp. 46\u201359. Springer, Cham (2022). https:\/\/doi.org\/10.1007\/978-3-031-06678-8_4"},{"key":"1147_CR2","unstructured":"Aichholzer, O., Fabila-Monroy, R., Kindermann, P., Parada, I., Paul, R., Perz, D., Schnider, P., Vogtenhuber, B.: In: Abstracts of the Computational Geometry: Young Researchers Forum, pp. 24\u201327 (2021). https:\/\/cse.buffalo.edu\/socg21\/files\/YRF-Booklet.pdf#page=24"},{"key":"1147_CR3","unstructured":"Asinowski, A.:The number of non-crossing perfect plane matchings is minimized (almost) only by point sets in convex position. arXiv preprint arXiv:1502.05332 (2015)"},{"key":"1147_CR4","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1016\/j.comgeo.2017.05.006","volume":"68","author":"A Asinowski","year":"2018","unstructured":"Asinowski, A., Rote, G.: Point sets with many non-crossing perfect matchings. Comput. Geom. 68, 7\u201333 (2018). https:\/\/doi.org\/10.1016\/j.comgeo.2017.05.006","journal-title":"Comput. Geom."},{"issue":"4","key":"1147_CR5","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/S0925-7721(00)00010-9","volume":"16","author":"A Garc\u00eda","year":"2000","unstructured":"Garc\u00eda, A., Noy, M., Tejel, J.: Lower bounds on the number of crossing-free subgraphs of $$K_n$$. Comput. Geom. 16(4), 211\u2013221 (2000). https:\/\/doi.org\/10.1016\/S0925-7721(00)00010-9","journal-title":"Comput. Geom."},{"issue":"3","key":"1147_CR6","doi-asserted-by":"publisher","first-page":"695","DOI":"10.1137\/050636036","volume":"36","author":"M Sharir","year":"2006","unstructured":"Sharir, M., Welzl, E.: On the number of crossing-free matchings, cycles, and partitions. SIAM J. Comput. 36(3), 695\u2013720 (2006). https:\/\/doi.org\/10.1137\/050636036","journal-title":"SIAM J. Comput."},{"key":"1147_CR7","unstructured":"You, C.: Improving Sharir and Welzl\u2019s bound on crossing-free matchings through solving a stronger recurrence. arXiv preprint arXiv:1701.05909 (2017)"},{"key":"1147_CR8","unstructured":"Callan, D.: A combinatorial survey of identities for the double factorial (2009)"},{"key":"1147_CR9","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/BF01215345","volume":"14","author":"B Aronov","year":"1994","unstructured":"Aronov, B., Erd\u0151s, P., Goddard, W., Kleitman, D.J., Klugerman, M., Pach, J., Schulman, L.J.: Crossing families. Combinatorica 14, 127\u2013134 (1994). https:\/\/doi.org\/10.1007\/BF01215345","journal-title":"Combinatorica"},{"key":"1147_CR10","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2022.101899","volume":"107","author":"O Aichholzer","year":"2022","unstructured":"Aichholzer, O., Kyn\u010dl, J., Scheucher, M., Vogtenhuber, B., Valtr, P.: On crossing-families in planar point sets. Comput. Geom. 107, 101899 (2022). https:\/\/doi.org\/10.1016\/j.comgeo.2022.101899","journal-title":"Comput. Geom."},{"key":"1147_CR11","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2021.107779","volume":"386","author":"J Pach","year":"2021","unstructured":"Pach, J., Rubin, N., Tardos, G.: Planar point sets determine many pairwise crossing segments. Adv. Math. 386, 107779 (2021). https:\/\/doi.org\/10.1016\/j.aim.2021.107779","journal-title":"Adv. Math."},{"key":"1147_CR12","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1090\/conm\/223","volume":"223","author":"J Pach","year":"1999","unstructured":"Pach, J., Solymosi, J.: Halving lines and perfect cross-matchings. Adv. Discrete Comput. Geom. 223, 245\u2013249 (1999). https:\/\/doi.org\/10.1090\/conm\/223","journal-title":"Adv. Discrete Comput. Geom."},{"key":"1147_CR13","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1007\/978-3-662-04166-6_17","volume-title":"Formal Power Series and Algebraic Combinatorics","author":"P Flajolet","year":"2000","unstructured":"Flajolet, P., Noy, M.: Analytic combinatorics of chord diagrams. In: Krob, D., Mikhalev, A.A., Mikhalev, A.V. (eds.) Formal Power Series and Algebraic Combinatorics, pp. 191\u2013201. Springer, Berlin (2000). https:\/\/doi.org\/10.1007\/978-3-662-04166-6_17"},{"key":"1147_CR14","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1016\/j.aam.2014.04.001","volume":"57","author":"V Pilaud","year":"2014","unstructured":"Pilaud, V., Rue, J.: Analytic combinatorics of chord and hyperchord diagrams with $$k$$ crossings. Adv. Appl. Math. 57, 60\u2013100 (2014). https:\/\/doi.org\/10.1016\/j.aam.2014.04.001","journal-title":"Adv. Appl. Math."},{"issue":"129","key":"1147_CR15","doi-asserted-by":"publisher","first-page":"215","DOI":"10.2307\/2005477","volume":"29","author":"J Riordan","year":"1975","unstructured":"Riordan, J.: The distribution of crossings of chords joining pairs of $$2n$$ points on a circle. Math. Comput. 29(129), 215\u2013222 (1975). https:\/\/doi.org\/10.2307\/2005477","journal-title":"Math. Comput."},{"key":"1147_CR16","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1023\/A:1021231927255","volume":"19","author":"O Aichholzer","year":"2002","unstructured":"Aichholzer, O., Aurenhammer, F., Krasser, H.: Enumerating order types for small point sets with applications. Order 19, 265\u2013281 (2002). https:\/\/doi.org\/10.1023\/A:1021231927255","journal-title":"Order"},{"key":"1147_CR17","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1016\/j.endm.2008.01.047","volume":"30","author":"BM \u00c1brego","year":"2008","unstructured":"\u00c1brego, B.M., Fern\u00e1ndez-Merchant, S., Lea\u00f1os, J., Salazar, G.: A central approach to bound the number of crossings in a generalized configuration. Electron. Not. Discrete Math. 30, 273\u2013278 (2008). https:\/\/doi.org\/10.1016\/j.endm.2008.01.047","journal-title":"Electron. Not. Discrete Math."},{"issue":"1","key":"1147_CR18","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/s00373-007-0704-5","volume":"23","author":"O Aichholzer","year":"2007","unstructured":"Aichholzer, O., Hackl, T., Huemer, C., Hurtado, F., Krasser, H., Vogtenhuber, B.: On the number of plane geometric graphs. Graphs Combin. 23(1), 67\u201384 (2007). https:\/\/doi.org\/10.1007\/s00373-007-0704-5","journal-title":"Graphs Combin."},{"key":"1147_CR19","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1090\/conm\/453\/08804","volume":"453","author":"G Nivasch","year":"2008","unstructured":"Nivasch, G.: An improved, simple construction of many halving edges. Contemp. Math. 453, 299\u2013306 (2008)","journal-title":"Contemp. Math."},{"key":"1147_CR20","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1007\/PL00009354","volume":"19","author":"TK Dey","year":"1998","unstructured":"Dey, T.K.: Improved bounds for planar k-sets and related problems. Discrete Comput. Geom. 19, 373\u2013382 (1998)","journal-title":"Discrete Comput. Geom."},{"issue":"4","key":"1147_CR21","doi-asserted-by":"publisher","first-page":"1210","DOI":"10.1007\/s00454-020-00251-7","volume":"64","author":"D Eppstein","year":"2020","unstructured":"Eppstein, D.: Counting polygon triangulations is hard. Discrete Comput. Geom. 64(4), 1210\u20131234 (2020). https:\/\/doi.org\/10.1007\/s00454-020-00251-7","journal-title":"Discrete Comput. Geom."},{"issue":"3","key":"1147_CR22","doi-asserted-by":"publisher","first-page":"771","DOI":"10.1007\/s00454-013-9538-5","volume":"50","author":"S Cabello","year":"2013","unstructured":"Cabello, S., Cardinal, J., Langerman, S.: The clique problem in ray intersection graphs. Discrete Comput. Geom. 50(3), 771\u2013783 (2013). https:\/\/doi.org\/10.1007\/s00454-013-9538-5","journal-title":"Discrete Comput. Geom."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01147-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-023-01147-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01147-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,11]],"date-time":"2024-03-11T11:10:29Z","timestamp":1710155429000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-023-01147-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,18]]},"references-count":22,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,3]]}},"alternative-id":["1147"],"URL":"https:\/\/doi.org\/10.1007\/s00453-023-01147-7","relation":{"has-preprint":[{"id-type":"doi","id":"10.21203\/rs.3.rs-2120588\/v1","asserted-by":"object"}]},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,7,18]]},"assertion":[{"value":"30 September 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 June 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 July 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"No competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics Approval"}},{"value":"Not applicable.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent to Participate"}},{"value":"Not applicable.","order":5,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for Publication"}}]}}