The k-relative neighborhood graph (k-RNG) is defined on a set of points P in the plane. There is an edge between two points p and q in P iff the lune between p and q contains at most k points of P inside. The k-RNG contains m=O(kn) edges; this improves the running time of the following bottleneck problems. We show that a bottleneck perfect matching of P is contained in 17-RNG, and it can be computed in O(m(n log n)^0.5). We show that a bottleneck biconnected subgraph of P is contained in 2-RNG, and it can be computed in O(m log n). We also show that a bottleneck Hamiltonian cycle is contained in 20-RNG. Finally, we show how to compute k-RNG.

The talk is a summary of these papers:

[1] M.-S. Chang, C. Y. Tang, and R. C. T. Lee.
20-relative neighborhood graphs are Hamiltonian.
Journal of Graph Theory, 15(5):543-557, 1991.

[2] M.-S. Chang, C. Y. Tang, and R. C. T. Lee.
Solving the Euclidean bottleneck biconnected edge subgraph problem by 2-relative neighborhood graphs.
Discrete Applied Mathematics, 39(1):1-12, 1992.

[3] M.-S. Chang, C. Y. Tang, and R. C. T. Lee.
Solving the Euclidean bottleneck matching problem by k-relative neighborhood graphs.
Algorithmica, 8(3):177-194, 1992.