Finding Hamiltonian cycles in Delaunay triangulations is NP-complete
type: Item
instance of: scholarly article
title: Finding Hamiltonian cycles in Delaunay triangulations is NP-complete
zbMATH Open document ID: 0852.05061
DOI: 10.1016/0166-218X(94)00125-W
author: Michael B. Dillencourt
published in: Discrete Applied Mathematics
publication date: 1996-08-04T00:00:00Z
review text: 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.
reviewed by: Martin Knor
Mathematics Subject Classification ID: 05C45
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 68U05
zbMATH DE Number: 897363
zbMATH Keywords: NP-complete problem
zbMATH Keywords: Delaunay triangulation
zbMATH Keywords: inscribable polyhedron
zbMATH Keywords: Hamiltonian cycle
zbMATH Keywords: 2-factors
MaRDI profile type: Publication
cites work: Q3888545
cites work: Q5422499
cites work: Voronoi diagrams from convex hulls
cites work: Q3689218
cites work: Finding Hamiltonian cycles in certain planar graphs
cites work: On certain Hamiltonian inner triangulations
cites work: Q5573028
cites work: A non-Hamiltonian, nondegenerate Delaunay triangulation
cites work: An upper bound on the shortness exponent of inscribable polytopes
cites work: Hamiltonian cycles in planar triangulations with no separating triangles
cites work: Toughness and Delaunay triangulations
cites work: Graph-theoretical conditions for inscribability and Delaunay realizability
cites work: Q3772828
cites work: A characterization of convex hyperbolic polyhedra and of convex polyhedra inscribed in the sphere
cites work: Traveling salesman cycles are not always subgraphs of Voronoi duals
cites work: Connectivity of plane triangulations
cites work: Q4763337
cites work: Some problems in computational geometry
cites work: Q5528475
cites work: Connect-the-dots: A new heuristic
cites work: Q3992847
cites work: Fast Heuristics for Large Geometric Traveling Salesman Problems
cites work: On geometry of convex ideal polyhedra in hyperbolic 3-space
cites work: 4-connected projective planar graphs are Hamiltonian
cites work: A theorem on paths in planar graphs
cites work: The Factors of Graphs
cites work: A Theorem on Planar Graphs
description: scientific article; zbMATH DE number 897363