Deviation Estimates for Extremal Relay Random Geometric Graphs

In this paper, we consider a deterministic graph~$\mathrm{\Gamma }$ drawn on the unit square with straight line segments as edges and connect vertices of~$\mathrm{\Gamma }$ using edges of a random geometric graph (RGG)~$G$ with adjacency distance~$r_n$ as relays. We call the resulting graph as a \emph{relay} RGG and determine sufficient conditions under such relay RGGs exist and are also near optimal, in terms of the graph parameters of~$\mathrm{\Gamma }\mathrm{.}$ We then equip edges of~$G$ with independent, exponentially distributed weights and obtain bounds for the maximum possible weight~$W_n$ of a relay RGG with a given length~$L_n\mathrm{.}$