Edge-Constrained Hamiltonian Paths on a Point Set
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909936802332672 |
|---|---|
| author | Antić, Todor Džuklevski, Aleksa Fiala, Jiří Kratochvíl, Jan Liotta, Giuseppe Saghafian, Morteza Saumell, Maria Zink, Johannes |
| author_facet | Antić, Todor Džuklevski, Aleksa Fiala, Jiří Kratochvíl, Jan Liotta, Giuseppe Saghafian, Morteza Saumell, Maria Zink, Johannes |
| contents | 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 ab, where a, b in S. We consider the following scenarios: (i) ab in pi; (ii) ab not in pi. We characterize those quintuples (S, a, b, s, t) 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 ab, where a, b in S. We consider the following scenarios: (i) pi_1 and pi_2 share no edges and ab is an edge of pi_1; (ii) pi_1 and pi_2 share no edges and none of them includes ab as an edge; (iii) both pi_1 and pi_2 include ab as an edge and share no other edges. In all cases, we characterize those triples (S, a, b) for which pi_1 and pi_2 exist. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_22526 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Edge-Constrained Hamiltonian Paths on a Point Set Antić, Todor Džuklevski, Aleksa Fiala, Jiří Kratochvíl, Jan Liotta, Giuseppe Saghafian, Morteza Saumell, Maria Zink, Johannes Computational Geometry 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 ab, where a, b in S. We consider the following scenarios: (i) ab in pi; (ii) ab not in pi. We characterize those quintuples (S, a, b, s, t) 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 ab, where a, b in S. We consider the following scenarios: (i) pi_1 and pi_2 share no edges and ab is an edge of pi_1; (ii) pi_1 and pi_2 share no edges and none of them includes ab as an edge; (iii) both pi_1 and pi_2 include ab as an edge and share no other edges. In all cases, we characterize those triples (S, a, b) for which pi_1 and pi_2 exist. |
| title | Edge-Constrained Hamiltonian Paths on a Point Set |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2511.22526 |