×

A note on two geometric paths with few crossings for points labeled by integers in the plane. (English) Zbl 1380.05039

Summary: Let \(S\) be a set of \(n\) points in the plane in general position such that the integers \(1, 2, \dotsc, n\) are assigned to the points bijectively. Set \(h\) be an integer with \(1 \leq h < n(n + 1)/2\). In this paper we consider the problem of finding two vertex-disjoint simple geometric paths consisting of all points of \(S\) such that the sum of labels of the points in one path is equal to \(h\) and the paths have as few crossings as possible. We prove that there exists such a pair of paths with at most two crossings between them.

MSC:

05C10 Planar graphs; geometric and topological aspects of graph theory
05C38 Paths and cycles
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aichholzer, O.; Aurenhammer, F.; Hackl, T.; Huemer, C., Connecting colored point sets, Discrete Appl. Math., 155, 271-278 (2007) · Zbl 1108.68122
[2] Araujo, G.; Balogh, J.; Fabila, R.; Salazar, G.; Urrutia, J., A note on harmonic subgraphs in labelled geometric graphs, Inform. Process. Lett., 105, 98-102 (2008) · Zbl 1184.68553
[3] Balogh, J.; Pittel, B.; Salazar, G., Large harmonic sets of noncrossing edges for \(n\) randomly labeled vertices in convex position, Random Structures Algorithms, 30, 105-130 (2007) · Zbl 1109.05094
[4] Kaneko, A.; Kano, M., Discrete geometry on red and blue points in the plane - A survey, (Discrete and Computational Geometry - The Goodman-Pollack Festschrift (2003), Springer-Verlag), 551-570 · Zbl 1079.52505
[5] Kano, M.; Merino, C.; Urrutia, J., On plane spanning trees and cycles of multicolored point sets with few intersections, Inform. Process. Lett., 93, 301-306 (2005) · Zbl 1173.68606
[6] Merino, C.; Salazar, G.; Urrutia, J., On the intersection number of matchings and minimum weight perfect matchings of multicolored point sets, Graphs Combin., 21, 333-341 (2005) · Zbl 1075.05076
[7] Pach, J., Geometric graph theory, (Surveys in Combinatorics, 1999. Surveys in Combinatorics, 1999, London Math. Soc. Lecture Note Ser., vol. 267 (1999), Cambridge Univ. Press), 167-200 · Zbl 0931.05024
[8] Tokunaga, S., Intersection number of two connected geometric graphs, Inform. Process. Lett., 59, 331-333 (1996) · Zbl 0900.68426
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.