Percolation thresholds on planar Euclidean relative neighborhood graphs

Abstract

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.

7 pages, 5 figures, 1 table

References in corpus (14)

• A fast Monte Carlo algorithm for site or bond percolation
• Efficient Monte Carlo algorithm and high-precision results for percolation
• Continuum Percolation Thresholds in Two Dimensions
• Low-temperature behavior of two-dimensional Gaussian Ising spin glasses
• Exact Site Percolation Thresholds Using the Site-to-Bond and Star-Triangle Transformations
• Percolation thresholds on 2D Voronoi networks and Delaunay triangulations
• Fractal dimension of domain walls in two-dimensional Ising spin glasses
• Universal condition for critical percolation thresholds of kagome-like lattices
• Domain walls and chaos in the disordered SOS model
• Critical properties of loop percolation models with optimization constraints
• Negative-weight percolation
• Superconductor-to-Normal Phase Transition in a Vortex Glass Model: Numerical Evidence for a New Percolation Universality Class
• The upper critical dimension of the negative-weight percolation problem
• Site Percolation on Planar ${\Phi }^3$ Random Graphs

Cited by in corpus (5)

• Efficient Cluster Algorithm for Spin Glasses in Any Space Dimension
• borealis - A generalized global update algorithm for Boolean optimization problems
• Dimer Covering and Percolation Frustration
• Fragmentation properties of two-dimensional Proximity Graphs considering random failures and targeted attacks
• Explosive dismantling of two-dimensional random lattices under betweenness centrality attacks