Edge-Constrained Hamiltonian Paths on a Point Set
摘要
Let S be a set of distinct points in general position in the Euclidean plane. A plane Hamiltonian path on S is a crossing-free geometric path such that every point of S is a vertex of the path. It is known that, if S is sufficiently large, there exist three edge-disjoint plane Hamiltonian paths on S. In this paper we study an edge-constrained version of the problem of finding Hamiltonian paths on a point set. We first consider the problem of finding a single plane Hamiltonian path \(\pi \) with endpoints \(s,t \in S\) and constraints given by a segment \(\overline{ab}\) , where \(a,b\in S\) . We consider the following scenarios: (i) \(\overline{ab} \in \pi \) ; (ii) \(\overline{ab}\not \in \pi \) . We characterize those quintuples \(\langle S,a,b,s,t\rangle \) for which \(\pi \) exists. Secondly, we consider the problem of finding two plane Hamiltonian paths \(\pi _1,\pi _2\) on a set S with constraints given by a segment \(\overline{ab}\) , where \(a,b\in S\) . We consider the following scenarios: (i) \(\pi _1\) and \(\pi _2\) share no edges and \(\overline{ab}\) is an edge of \(\pi _1\) ; (ii) \(\pi _1\) and \(\pi _2\) share no edges and none of them includes \(\overline{ab}\) as an edge; (iii) both \(\pi _1\) and \(\pi _2\) include \(\overline{ab}\) as an edge and share no other edges. In all cases, we characterize those triples \(\langle S,a,b \rangle \) for which \(\pi _1\) and \(\pi _2\) exist.