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 . π with endpoints .s, t ∈ S and constraints given by a segment . ab, where .a, b ∈ S. We consider the following scenarios: (i) .ab ∈ π; (ii) .ab π. We characterize those quintuples . S, a, b, s, t for which . π exists. Secondly, we consider the problem of finding two plane Hamiltonian paths . π1, π2 on a set . S with constraints given by a segment . ab, where .a, b ∈ S. We consider the following scenarios: (i) .π1 and .π2 share no edges and .ab is an edge of . π1; (ii) .π1 and .π2 share no edges and none of them includes .ab as an edge; (iii) both .π1 and .π2 include .ab as an edge and share no other edges. In all cases, we characterize those triples . S, a, b for which .π1 and .π2 exist.