Abstract
Let P and Q be disjoint point sets with 2r and 2s elements respectively, and M1 and M2 be their minimum weight perfect matchings (with respect to edge lengths). We prove that the edges of M1 and M2 intersect at most |M1|+|M2|−1 times. This bound is tight. We also prove that P and Q have perfect matchings (not necessarily of minimum weight) such that their edges intersect at most min{r,s} times. This bound is also sharp.
Similar content being viewed by others
References
Abellanas, M., García, J., Hernández, G., Noy, M., Ramos, P.: Bipartite embeddings of trees in the plane. Graph Drawing 96 (Lect. Notes Comput. Sci. 1990, pp. 1–10) Berlin: Springer-Verlag 1997
Akiyama, J., Urrutia, J.: Simple alternating path problems. Discrete Math. 84, 101–103 (1990)
Dumitrescu, A., Pach, J.: Partitioning colored point sets into monochromatic parts. Int. J. Comput. Geom. Appl. 12(5), 401–412 (2002)
Dumitrescu, A., Kaye, R.: Matching colored points in the plane, some new results. Comput. Geom. Theory Appl. 19(1), 69–85 (2001)
Dumitrescu, A., Steiger, W.: On a matching problem on the plane. Discrete Math. 211, 183–195 (2000)
Kano, M., Merino, C., Urrutia, J.: On spanning trees and cycles of multicolored point sets with few intersections. Inf. Process. Lett. 93, 301–306 (2005)
Karoli, G., Pach, J., Tóth, G.: Ramsey-type results for geometric graphs, I. Discrete Comput. Geom. 18, 247–255 (1995)
Karoli, G., Pach, J., Tóth, G., Valtr, P.: Ramsey-type results for geometric graphs, II. Discrete Comput. Geom. 20, 375–388 (1998)
Pach, J.: Geometric graph theory. J.D. Lamb and D. Preece: Surveys in combinatorics, Canterbury 1999 (Lond. Math. Soc. Lect. Note Ser., vol. 267, pp. 167–200) Cambridge.: Cambridge Univ. Press 1999
Tokunaga, S.: Crossing number of two-connected geometric graphs. Inf. Process. Lett 59, 331–333 (1996)
Author information
Authors and Affiliations
Corresponding authors
Additional information
Supported by PAPIIT(UNAM) of México, Proyecto IN110802
Supported by FAI-UASLP and by CONACYT of México, Proyecto 32168-E
Supported by CONACYT of México, Proyecto 37540-A
Rights and permissions
About this article
Cite this article
Merino, C., Salazar, G. & Urrutia, J. On the Intersection Number of Matchings and Minimum Weight Perfect Matchings of Multicolored Point Sets. Graphs and Combinatorics 21, 333–341 (2005). https://doi.org/10.1007/s00373-004-0606-8
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/s00373-004-0606-8