---
OA_place: repository
OA_type: green
_id: '21374'
abstract:
- lang: eng
  text: "Let . S be a set of distinct points in general position in the\r\nEuclidean
    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\r\nknown that, if. S is
    sufficiently large, there exist three edge-disjoint plane\r\nHamiltonian paths
    on . S. In this paper we study an edge-constrained\r\nversion of the problem of
    finding Hamiltonian paths on a point set. We\r\nfirst consider the problem of
    finding a single plane Hamiltonian path . π\r\nwith endpoints .s, t ∈ S and constraints
    given by a segment . ab, where\r\n.a, b ∈ S. We consider the following scenarios:
    (i) .ab ∈ π; (ii) .ab π. We\r\ncharacterize those quintuples . S, a, b, s, t for
    which . π exists. Secondly,\r\nwe consider the problem of finding two plane Hamiltonian
    paths . π1, π2\r\non a set . S with constraints given by a segment . ab, where
    .a, b ∈ S. We\r\nconsider the following scenarios: (i) .π1 and .π2 share no edges
    and .ab is\r\nan edge of . π1; (ii) .π1 and .π2 share no edges and none of them
    includes\r\n.ab as an edge; (iii) both .π1 and .π2 include .ab as an edge and
    share no\r\nother edges. In all cases, we characterize those triples . S, a, b
    for which\r\n.π1 and .π2 exist."
acknowledgement: "We thank the organizers of the HOMONOLO 2024 workshop in Nová Louka,
  Czech Republic, for the fruitful atmosphere where the research on this project was
  initiated.\r\n\r\nT. Antić, A. Džuklevski, J. Kratochvíl and M. Saumell received
  funding from GAČR grant 23–04949X, T.A and A.Dž were additionally supported by GAUK
  grant SVV–2025–260822. G. Liotta was supported in part by MUR of Italy, PRIN Project
  no. 2022TS4Y3N – EXPAND and PON Project ARS01_00540. J. Fiala was in part supported
  by GAČR grant 25-16847S."
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Todor
  full_name: Antić, Todor
  last_name: Antić
- first_name: Aleksa
  full_name: Džuklevski, Aleksa
  last_name: Džuklevski
- first_name: Jiří
  full_name: Fiala, Jiří
  last_name: Fiala
- first_name: Jan
  full_name: Kratochvíl, Jan
  last_name: Kratochvíl
- first_name: Giuseppe
  full_name: Liotta, Giuseppe
  last_name: Liotta
- first_name: Morteza
  full_name: Saghafian, Morteza
  id: f86f7148-b140-11ec-9577-95435b8df824
  last_name: Saghafian
- first_name: Maria
  full_name: Saumell, Maria
  last_name: Saumell
- first_name: Johannes
  full_name: Zink, Johannes
  last_name: Zink
citation:
  ama: 'Antić T, Džuklevski A, Fiala J, et al. Edge-constrained Hamiltonian paths
    on a point set. In: <i>51st International Conference on Current Trends in Theory
    and Practice of Computer Science</i>. Vol 16448. Springer Nature; 2026:532-546.
    doi:<a href="https://doi.org/10.1007/978-3-032-17801-5_39">10.1007/978-3-032-17801-5_39</a>'
  apa: 'Antić, T., Džuklevski, A., Fiala, J., Kratochvíl, J., Liotta, G., Saghafian,
    M., … Zink, J. (2026). Edge-constrained Hamiltonian paths on a point set. In <i>51st
    International Conference on Current Trends in Theory and Practice of Computer
    Science</i> (Vol. 16448, pp. 532–546). Krakow, Poland: Springer Nature. <a href="https://doi.org/10.1007/978-3-032-17801-5_39">https://doi.org/10.1007/978-3-032-17801-5_39</a>'
  chicago: Antić, Todor, Aleksa Džuklevski, Jiří Fiala, Jan Kratochvíl, Giuseppe Liotta,
    Morteza Saghafian, Maria Saumell, and Johannes Zink. “Edge-Constrained Hamiltonian
    Paths on a Point Set.” In <i>51st International Conference on Current Trends in
    Theory and Practice of Computer Science</i>, 16448:532–46. Springer Nature, 2026.
    <a href="https://doi.org/10.1007/978-3-032-17801-5_39">https://doi.org/10.1007/978-3-032-17801-5_39</a>.
  ieee: T. Antić <i>et al.</i>, “Edge-constrained Hamiltonian paths on a point set,”
    in <i>51st International Conference on Current Trends in Theory and Practice of
    Computer Science</i>, Krakow, Poland, 2026, vol. 16448, pp. 532–546.
  ista: 'Antić T, Džuklevski A, Fiala J, Kratochvíl J, Liotta G, Saghafian M, Saumell
    M, Zink J. 2026. Edge-constrained Hamiltonian paths on a point set. 51st International
    Conference on Current Trends in Theory and Practice of Computer Science. SOFSEM:
    Conference on Current Trends in Theory and Practice of Computer Science, LNCS,
    vol. 16448, 532–546.'
  mla: Antić, Todor, et al. “Edge-Constrained Hamiltonian Paths on a Point Set.” <i>51st
    International Conference on Current Trends in Theory and Practice of Computer
    Science</i>, vol. 16448, Springer Nature, 2026, pp. 532–46, doi:<a href="https://doi.org/10.1007/978-3-032-17801-5_39">10.1007/978-3-032-17801-5_39</a>.
  short: T. Antić, A. Džuklevski, J. Fiala, J. Kratochvíl, G. Liotta, M. Saghafian,
    M. Saumell, J. Zink, in:, 51st International Conference on Current Trends in Theory
    and Practice of Computer Science, Springer Nature, 2026, pp. 532–546.
conference:
  end_date: 2026-02-13
  location: Krakow, Poland
  name: 'SOFSEM: Conference on Current Trends in Theory and Practice of Computer Science'
  start_date: 2026-02-09
date_created: 2026-03-01T23:01:40Z
date_published: 2026-02-13T00:00:00Z
date_updated: 2026-03-02T08:49:20Z
day: '13'
department:
- _id: HeEd
doi: 10.1007/978-3-032-17801-5_39
external_id:
  arxiv:
  - '2511.22526'
intvolume: '     16448'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.2511.22526
month: '02'
oa: 1
oa_version: Preprint
page: 532-546
publication: 51st International Conference on Current Trends in Theory and Practice
  of Computer Science
publication_identifier:
  eissn:
  - 1611-3349
  isbn:
  - '9783032178008'
  issn:
  - 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Edge-constrained Hamiltonian paths on a point set
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 16448
year: '2026'
...