Percolation thresholds on planar Euclidean relative neighborhood graphs

O. Melchert

Published 2013-01-29Version 1

In the presented article, statistical properties regarding the topology and standard percolation on relative neighborhood graphs (RNGs) for planar sets of points, considering the Euclidean metric, are put under scrutiny. RNGs belong to the family of ``proximity graphs'', i.e. their edge-set encodes proximity information regarding the close neighbors for the terminal nodes of a given edge. Therefore they are, e.g., discussed in the context of the construction of backbones for wireless ad-hoc networks that guarantee connectedness of all underlying nodes. Here, by means of numerical simulations, we determine the asymptotic degree and diameter of RNGs and we estimate their bond and site percolation thresholds, which were previously conjectured to be nontrivial. We compare the results to regular 2D graphs for which the degree is close to that of the RNG. Finally, we deduce the common percolation critical exponents from the RNG data to verify that the associated universality class is that of standard 2D percolation.