20-relative neighborhood graphs are hamiltonian

✍ Scribed by M. S. Chang; C. Y. Tang; R. C. T. Lee

• Publisher: John Wiley and Sons
• Year: 1991
• Tongue: English
• Weight: 548 KB
• Volume: 15
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.3190150507

✦ Synopsis

Abstract

For any two points p and q in the Euclidean plane, define LUN~pq~ = {v|v ∈ R^2^, d~pv~ < d~pq~ and d~qv~ < d~pq~}, where d~uv~ is the Euclidean distance between two points u and v. Given a set of points V in the plane, let LUN~pq~(V) = V ∩ LUN~pq~. Toussaint defined the relative neighborhood graph of V, denoted by RNG(V) or simply RNG, to be the undirected graph with vertices V such that for each pair p,q ∈ V, (p,q) is an edge of RNG(V) if and only if LUN~pq~ (V) = ϕ. The relative neighborhood graph has several applications in pattern recognition that have been studied by Toussaint. We shall generalize the idea of RNG to define the k‐relative neighborhood graph of V, denoted by __k__RNG(V) or simply __k__RNG, to be the undirected graph with vertices V such that for each pair p,q ∈ V, (p,q) is an edge of __k__RNG(V) if and only if | LUN~pq~(V) | < k, for some fixed positive number k. It can be shown that the number of edges of a __k__RNG is less than O(kn). Also, a __k__RNG can be constructed in O(kn~2~) time. Let E~c~ = {e~pq~| p ∈ V and q ∈ V}. Then G~c~ = (V,E~c~) is a complete graph. For any subset F of E~c~, define the maximum distance of F as max~e~~pq~~∈F~d~pq~. A Euclidean bottleneck Hamiltonian cycle is a Hamiltonian cycle in graph G~c~ whose maximum distance is the minimum among all Hamiltonian cycles in graph G~c~. We shall prove that there exists a Euclidean bottleneck Hamiltonian cycle which is a subgraph of 20RNG(V). Hence, 20RNGs are Hamiltonian.