Finding Hamiltonian cycles in Delaunay triangulations is NP-complete
From MaRDI portal
Publication:1917249
DOI10.1016/0166-218X(94)00125-WzbMath0852.05061MaRDI QIDQ1917249
Publication date: 4 August 1996
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Planar graphs; geometric and topological aspects of graph theory (05C10) Eulerian and Hamiltonian graphs (05C45)
Related Items
Novel concave hull-based heuristic algorithm for TSP ⋮ The number of defective colorings of graphs on surfaces ⋮ Graph-theoretical conditions for inscribability and Delaunay realizability ⋮ Forest-like abstract Voronoi diagrams in linear time ⋮ Matching points with squares
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Toughness and Delaunay triangulations
- Connectivity of plane triangulations
- Finding Hamiltonian cycles in certain planar graphs
- Traveling salesman cycles are not always subgraphs of Voronoi duals
- Some problems in computational geometry
- A non-Hamiltonian, nondegenerate Delaunay triangulation
- An upper bound on the shortness exponent of inscribable polytopes
- Voronoi diagrams from convex hulls
- 4-connected projective planar graphs are Hamiltonian
- Graph-theoretical conditions for inscribability and Delaunay realizability
- On geometry of convex ideal polyhedra in hyperbolic 3-space
- On certain Hamiltonian inner triangulations
- A Theorem on Planar Graphs
- Connect-the-dots: A new heuristic
- A characterization of convex hyperbolic polyhedra and of convex polyhedra inscribed in the sphere
- Fast Heuristics for Large Geometric Traveling Salesman Problems
- Hamiltonian cycles in planar triangulations with no separating triangles
- The Factors of Graphs
- A theorem on paths in planar graphs
