Bichromatic Perfect Matchings with Crossings

Oswin Aichholzer; Stefan Felsner; Rosna Paul; Manfred Scheucher; Birgit Vogtenhuber

doi:10.1007/978-3-031-49272-3_9

Bichromatic Perfect Matchings with Crossings

Oswin Aichholzer, Stefan Felsner, Rosna Paul^*, Manfred Scheucher, Birgit Vogtenhuber

^*Corresponding author for this work

Institute of Software Technology (7160)

Research output: Chapter in Book/Report/Conference proceeding › Conference paper › peer-review

Abstract

We consider bichromatic point sets with n red and n blue points and study straight-line bichromatic perfect matchings on them. We show that every such point set in convex position admits a matching with at least 3n28-n2+c crossings, for some -12≤c≤18. This bound is tight since for any k>3n28-n2+18 there exist bichromatic point sets that do not admit any perfect matching with k crossings.

Original language	English
Title of host publication	Graph Drawing and Network Visualization
Editors	Michael A. Bekos, Markus Chimani
Place of Publication	Cham
Publisher	Springer Nature Switzerland AG
Pages	124-132
Number of pages	9
Volume	14465
ISBN (Print)	978-3-031-49272-3
DOIs	https://doi.org/10.1007/978-3-031-49272-3_9
Publication status	Published - 2023
Event	31st International Symposium on Graph Drawing and Network Visualization: GD 2023 - Palermo, Italy Duration: 20 Sept 2023 → 22 Sept 2023

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Publisher	Springer Nature Switzerland
Volume	14465 LNCS
ISSN (Electronic)	0302-9743

Conference

Conference	31st International Symposium on Graph Drawing and Network Visualization
Country/Territory	Italy
City	Palermo
Period	20/09/23 → 22/09/23

Fields of Expertise

Information, Communication & Computing

Access to Document

10.1007/978-3-031-49272-3_9

Cite this

Aichholzer, O., Felsner, S., Paul, R., Scheucher, M., & Vogtenhuber, B. (2023). Bichromatic Perfect Matchings with Crossings. In M. A. Bekos, & M. Chimani (Eds.), Graph Drawing and Network Visualization (Vol. 14465, pp. 124-132). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14465 LNCS). Springer Nature Switzerland AG. https://doi.org/10.1007/978-3-031-49272-3_9

Bichromatic Perfect Matchings with Crossings. / Aichholzer, Oswin; Felsner, Stefan; Paul, Rosna et al.
Graph Drawing and Network Visualization. ed. / Michael A. Bekos; Markus Chimani. Vol. 14465 Cham: Springer Nature Switzerland AG, 2023. p. 124-132 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14465 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference paper › peer-review

Aichholzer, O, Felsner, S, Paul, R, Scheucher, M & Vogtenhuber, B 2023, Bichromatic Perfect Matchings with Crossings. in MA Bekos & M Chimani (eds), Graph Drawing and Network Visualization. vol. 14465, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 14465 LNCS, Springer Nature Switzerland AG, Cham, pp. 124-132, 31st International Symposium on Graph Drawing and Network Visualization, Palermo, Italy, 20/09/23. https://doi.org/10.1007/978-3-031-49272-3_9

Aichholzer O, Felsner S, Paul R, Scheucher M, Vogtenhuber B. Bichromatic Perfect Matchings with Crossings. In Bekos MA, Chimani M, editors, Graph Drawing and Network Visualization. Vol. 14465. Cham: Springer Nature Switzerland AG. 2023. p. 124-132. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-49272-3_9

Aichholzer, Oswin ; Felsner, Stefan ; Paul, Rosna et al. / Bichromatic Perfect Matchings with Crossings. Graph Drawing and Network Visualization. editor / Michael A. Bekos ; Markus Chimani. Vol. 14465 Cham : Springer Nature Switzerland AG, 2023. pp. 124-132 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{4b59d92f4747420cb5d644f45574feca,

title = "Bichromatic Perfect Matchings with Crossings",

abstract = "We consider bichromatic point sets with n red and n blue points and study straight-line bichromatic perfect matchings on them. We show that every such point set in convex position admits a matching with at least 3n28-n2+c crossings, for some -12≤c≤18. This bound is tight since for any k>3n28-n2+18 there exist bichromatic point sets that do not admit any perfect matching with k crossings.",

author = "Oswin Aichholzer and Stefan Felsner and Rosna Paul and Manfred Scheucher and Birgit Vogtenhuber",

year = "2023",

doi = "10.1007/978-3-031-49272-3_9",

language = "English",

isbn = "978-3-031-49272-3",

volume = "14465",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Nature Switzerland AG",

pages = "124--132",

editor = "Bekos, {Michael A.} and Markus Chimani",

booktitle = "Graph Drawing and Network Visualization",

address = "Switzerland",

note = "31st International Symposium on Graph Drawing and Network Visualization : GD 2023 ; Conference date: 20-09-2023 Through 22-09-2023",

}

TY - GEN

T1 - Bichromatic Perfect Matchings with Crossings

AU - Aichholzer, Oswin

AU - Felsner, Stefan

AU - Paul, Rosna

AU - Scheucher, Manfred

AU - Vogtenhuber, Birgit

PY - 2023

Y1 - 2023

N2 - We consider bichromatic point sets with n red and n blue points and study straight-line bichromatic perfect matchings on them. We show that every such point set in convex position admits a matching with at least 3n28-n2+c crossings, for some -12≤c≤18. This bound is tight since for any k>3n28-n2+18 there exist bichromatic point sets that do not admit any perfect matching with k crossings.

AB - We consider bichromatic point sets with n red and n blue points and study straight-line bichromatic perfect matchings on them. We show that every such point set in convex position admits a matching with at least 3n28-n2+c crossings, for some -12≤c≤18. This bound is tight since for any k>3n28-n2+18 there exist bichromatic point sets that do not admit any perfect matching with k crossings.

U2 - 10.1007/978-3-031-49272-3_9

DO - 10.1007/978-3-031-49272-3_9

M3 - Conference paper

SN - 978-3-031-49272-3

VL - 14465

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 124

EP - 132

BT - Graph Drawing and Network Visualization

A2 - Bekos, Michael A.

A2 - Chimani, Markus

PB - Springer Nature Switzerland AG

CY - Cham

T2 - 31st International Symposium on Graph Drawing and Network Visualization

Y2 - 20 September 2023 through 22 September 2023

ER -

Bichromatic Perfect Matchings with Crossings

Abstract

Publication series

Conference

Fields of Expertise

Access to Document

Fingerprint

Cite this