Bichromatic perfect matchings with crossings. (English) Zbl 07869499
Bekos, Michael A. (ed.) et al., Graph drawing and network visualization. 31st international symposium, GD 2023, Isola delle Femmine, Palermo, Italy, September 20–22, 2023. Revised selected papers. Part I. Cham: Springer. Lect. Notes Comput. Sci. 14465, 124-132 (2023).
Summary: 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 \(\frac{3n^2}{8}-\frac{n}{2}+c\) crossings, for some \(-\frac{1}{2} \le c \le \frac{1}{8} \). This bound is tight since for any \(k> \frac{3n^2}{8} -\frac{n}{2}+\frac{1}{8}\) there exist bichromatic point sets that do not admit any perfect matching with \(k\) crossings.
For the entire collection see [Zbl 1539.68006].
For the entire collection see [Zbl 1539.68006].
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
References:
| [1] | Aichholzer, O.; Barba, L.; Hackl, T.; Pilz, A.; Vogtenhuber, B., Linear transformation distance for bichromatic matchings, Comput. Geom., 68, 77-88, 2018 · Zbl 1380.05050 · doi:10.1016/j.comgeo.2017.05.003 |
| [2] | Aichholzer, O.; Bazgan, C.; Fernau, H., Perfect matchings with crossings, Combinatorial Algorithms, 46-59, 2022, Cham: Springer, Cham · Zbl 07577689 · doi:10.1007/978-3-031-06678-8_4 |
| [3] | Aichholzer, O., Felsner, S., Paul, R., Scheucher, M., Vogtenhuber, B.: Bichromatic perfect matchings with crossings (2023). arXiv:2309.00546v1 |
| [4] | Aichholzer, O., Hurtado, F., Vogtenhuber, B.: Compatible matchings for bichromatic plane straight-line graphs. In: Proceedings of EuroCG’12, pp. 257-260 (2012). https://www.eurocg.org/2012/booklet.pdf |
| [5] | Aloupis, G.; Barba, L.; Langerman, S.; Souvaine, DL, Bichromatic compatible matchings, Comput. Geom., 48, 8, 622-633, 2015 · Zbl 1316.05097 · doi:10.1016/j.comgeo.2014.08.009 |
| [6] | Asinowski, A., Miltzow, T., Rote, G.: Quasi-parallel segments and characterization of unique bichromatic matchings. J. Comput. Geom. 6(1), 185-219 (2015). doi:10.20382/jocg.v6i1a8 · Zbl 1405.68393 |
| [7] | Kano, M., Urrutia, J.: Discrete geometry on colored point sets in the plane – a survey. Graphs Comb. 37(1), 1-53 (2021). doi:10.1007/s00373-020-02210-8 · Zbl 1459.05032 |
| [8] | Pach, J.; Rubin, N.; Tardos, G., Planar point sets determine many pairwise crossing segments, Adv. Math., 386, 107779, 2021 · Zbl 1467.05050 · doi:10.1016/j.aim.2021.107779 |
| [9] | Savić, M.; Stojaković, M., Structural properties of bichromatic non-crossing matchings, Appl. Math. Comput., 415, 126695, 2022 · Zbl 1510.05244 |
| [10] | Sharir, M.; Welzl, E., On the number of crossing-free matchings, cycles, and partitions, SIAM J. Comput., 36, 3, 695-720, 2006 · Zbl 1120.68085 · doi:10.1137/050636036 |
| [11] | Tóth, C.D., O’Rourke, J., Goodman, J.E.: Handbook of Discrete and Computational Geometry. 3rd edn. CRC Press, Boca Raton (2017). doi:10.1201/9781315119601 · Zbl 1375.52001 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
