Finding Hamiltonian cycles in Delaunay triangulations is NP-complete
It is shown that it is an NP-complete problem to determine whether a nondegenerate Delaunay triangulation or an inscribable polyhedron has a Hamiltonian cycle. There are also constructed a nondegenerate Delaunay triangulation and a simplicial, inscribable polyhedron, without 2-factors.
scientific article; zbMATH DE number 897363
scientific article