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.