Loading...
Loading...

Go to the content (press return)

On Hamiltonian alternating cycles and paths

Author
Claverol, M.; García, A.; Garijo, D.; Seara, C.; Tejel, J.
Type of activity
Journal article
Journal
Computational geometry: theory and applications
Date of publication
2018-03
Volume
68
First page
146
Last page
166
DOI
https://doi.org/10.1016/j.comgeo.2017.05.009 Open in new window
Repository
http://hdl.handle.net/2117/112128 Open in new window
URL
http://www.sciencedirect.com/science/article/pii/S0925772117300421?via%3Dihub Open in new window
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 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 tha...
Citation
Claverol, M., García, A., Garijo, D., Seara, C., Tejel, J. On Hamiltonian alternating cycles and paths. "Computational geometry: theory and applications", Març 2018, vol. 68, p. 146-166.
Keywords
1-plane graphs, Bicolored point sets, Hamiltonian alternating cycles and paths, Minimum number of crossings
Group of research
CGA -Computational Geometry and Applications

Participants

Attachments