Abstract
Let S be a set of n points in the plane in general position such that the integers 1,2,…,n are assigned to the points bijectively. Set h be an integer with 1≤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.
Original language | English |
---|---|
Pages (from-to) | 1109-1113 |
Number of pages | 5 |
Journal | Discrete Mathematics |
Volume | 341 |
Issue number | 4 |
DOIs | |
Publication status | Published - 2018 Apr |
Keywords
- Geometric graph
- Geometric paths
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics