10-Gabriel graphs are Hamiltonian

DOI10.1016/j.ipl.2015.05.013zbMath1332.05082arXiv1410.0309OpenAlexW1837675489MaRDI QIDQ2353639

Maria Saumell, Tomáš Kaiser, Nicolas Van Cleemput

Publication date: 15 July 2015

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1410.0309

zbMATH Keywords

Hamiltonian cyclescomputational geometryGabriel graphsproximity graphs

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Connectivity (05C40)

Related Items (4)

Higher-order triangular-distance Delaunay graphs: graph-theoretical properties ⋮ Hamiltonicity for convex shape Delaunay and Gabriel graphs ⋮ Bottleneck matchings and Hamiltonian cycles in higher-order Gabriel graphs ⋮ Matchings in higher-order Gabriel graphs

Cites Work

• Unnamed Item
• Delaunay graphs are almost as good as complete graphs
• Matching points with squares
• A non-Hamiltonian, nondegenerate Delaunay triangulation
• The relative neighbourhood graph of a finite planar set
• Solving the Euclidean bottleneck matching problem by \(k\)-relative neighborhood graphs
• The densest packing of 12 congruent circles in a circle
• Voronoi Diagrams and Delaunay Triangulations
• ON STRUCTURAL AND GRAPH THEORETIC PROPERTIES OF HIGHER ORDER DELAUNAY GRAPHS
• On the Spanning Ratio of Gabriel Graphs and beta-Skeletons
• On the expected maximum degree of Gabriel and Yao graphs
• 20‐relative neighborhood graphs are hamiltonian
• PROXIMITY GRAPHS: E, δ, Δ, χ AND ω

This page was built for publication: 10-Gabriel graphs are Hamiltonian