Probabilistic Properties of Highly Connected Random Geometric Graphs

In this paper we study the probabilistic properties of reliable networks of minimal total edge lengths. We study reliability in terms of k-edge-connectivity in graphs in d-dimensional space. We show this problem fits into Yukich’s framework for Euclidean functionals for arbitrary k, dimension d and distant-power gradient p, with p < d. With this framework several theorems on the convergence of optimal solutions follow. We apply Yukich’s framework for functionals so that we can use partitioning algorithms that rapidly compute near-optimal solutions on typical examples. These results are then extended to optimal k-edge-connected power assignment graphs, where we assign power to vertices and charge per vertex. The network can be modelled as a wireless network.