Given a set P of n points in the plane, the order-k Gabriel graph on P, denoted by k-GG, has an edge between two points p and q if and only if the closed disk with diameter pq contains at most k points of P, excluding p and q. It is known that 10-GG contains a Euclidean bottleneck matching of P, while 8-GG may not contain such a matching. We answer the following question in the affirmative: does 9-GG contain any Euclidean bottleneck matching of P? Thereby, we close the gap for the containment problem of Euclidean bottleneck matchings in Gabriel graphs. It is also known that 10-GG contains a Euclidean bottleneck Hamiltonian cycle of P, while 5-GG may not contain such a cycle. We improve the lower bound and show that 7-GG may not contain any Euclidean bottleneck Hamiltonian cycle of P.

Additional Metadata
Keywords Computational geometry, Euclidean bottleneck matchings, Euclidean Hamiltonian cycles, Gabriel graphs
Persistent URL dx.doi.org/10.1016/j.ipl.2019.105869
Journal Information Processing Letters
Citation
Biniaz, A. (Ahmad), Maheshwari, A, & Smid, M. (2019). Bottleneck matchings and Hamiltonian cycles in higher-order Gabriel graphs. Information Processing Letters. doi:10.1016/j.ipl.2019.105869