We study Hamiltonicity for some of the most general variants of Delaunay and Gabriel graphs. Instead of defining these proximity graphs using circles, we use an arbitrary convex shape C. Let S be a point set in the plane. The k-order Delaunay graph of S, denoted k- DGC(S), has vertex set S and edge pq provided that there exists some homothet of C with p and q on its boundary and containing at most k points of S different from p and q. The k-order Gabriel graph k- GGC(S) is defined analogously, except for the fact that the homothets considered are restricted to be smallest homothets of C with p and q on its boundary. We provide upper bounds on the minimum value of k for which k- GGC(S) is Hamiltonian. Since k- GGC(S) ⊆ k- DGC(S), all results carry over to k- DGC(S). In particular, we give upper bounds of 24 for every C and 15 for every point-symmetric C. We also improve the bound to 7 for squares, 11 for regular hexagons, 12 for regular octagons, and 11 for even-sided regular t-gons (for t≥ 10). These constitute the first general results on Hamiltonicity for convex shape Delaunay and Gabriel graphs.

Additional Metadata
Persistent URL dx.doi.org/10.1007/978-3-030-24766-9_15
Series Lecture Notes in Computer Science
Bose, P, Cano, P. (Pilar), Saumell, M. (Maria), & Silveira, R.I. (Rodrigo I.). (2019). Hamiltonicity for convex shape delaunay and gabriel graphs. In Lecture Notes in Computer Science. doi:10.1007/978-3-030-24766-9_15