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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Edge-Constrained Hamiltonian Paths on a Point Set

  • Todor Antić,
  • Aleksa Džuklevski,
  • Jiří Fiala,
  • Jan Kratochvíl,
  • Giuseppe Liotta,
  • Morteza Saghafian,
  • Maria Saumell,
  • Johannes Zink

摘要

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.