Article
On Hamiltonian alternating cycles and paths
Author/s | Claverol, Mercé
García, Alfredo Garijo Royo, Delia Seara, Carlos Tejel, Javier |
Department | Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII) |
Publication Date | 2018 |
Deposit Date | 2020-06-19 |
Published in |
|
Abstract | We undertake a study on computing Hamiltonian alternating cycles and paths on bicolored
point sets. This has been an intensively studied problem, not always with a solution, when
the paths and cycles are also required ... We undertake a study on computing Hamiltonian alternating cycles and paths on bicolored point sets. This has been an intensively studied problem, not always with a solution, when the paths and cycles are also required to be plane. In this paper, we relax the constraint on the cycles and paths from being plane to being 1-plane, and deal with the same type of questions as those for the plane case, obtaining a remarkable variety of results. For point sets in general position, our main result is that it is always possible to obtain a 1-plane Hamiltonian alternating cycle. When the point set is in convex position, we prove that every Hamiltonian alternating cycle with minimum number of crossings is 1-plane, and provide O(n) and O(n2) time algorithms for computing, respectively, Hamiltonian alternating cycles and paths with minimum number of crossings. |
Funding agencies | Ministerio de Economía y Competitividad (MINECO). España |
Project ID. | MTM2014-60127-P |
Citation | Claverol, M., García, A., Garijo Royo, D., Seara, C. y Tejel, J. (2018). On Hamiltonian alternating cycles and paths. Computational Geometry, 68 (march 2018), 146-166. |
Files | Size | Format | View | Description |
---|---|---|---|---|
On Hamiltonian alternating.pdf | 531.8Kb | [PDF] | View/ | |