Question

The existence of a closed-form solution of the connectivity in terms of the radius of vertices (disks) in a two-dimensional (d=2) random geometric graph (RGG) with open boundary conditions. I know, from Dall & Christensen, 2002 that for continuous boundary conditions (i.e. periodic boundary conditions) one can express the connectivity κ in terms of the radius of the disks:

κ = NVex = 4πNr^2

when Vex = π⋅(2r)^2

the excluded volume of a disk with radius R = 2r. I have performed simulations that verify this.

However, when the boundaries are open instead (i.e. edges do not wrap around) the connectivity is lower; κopen < κ. I have been searching for a closed-form solution for the connectivity of RGGs with open boundaries, but I was not able to find it. However, it seems that the critical connectivity, i.e. the connectivity after which a giant component with O(N) vertices appears, is independent of the boundary conditions as N→[infinity]. Yet, one often wishes to plot quantities of the RGG versus its connectivity κ (see the figures in the mentioned paper), however in order to do this one needs to be able to compute κ from the given radius r, which I am clearly unable to do. I can do this numerically, but this does not enable me to generate graphs with a specific connectivity.

So, is there a closed-form solution for the connectivity in terms of the disks' radius r in two-dimensional systems with open boundary conditions?

Answer 1

There is no known closed-form solution for the connectivity of random geometric graphs in two-dimensional systems with open boundary conditions. The problem remains unsolved even as numerical simulation can provide estimates for specific cases.

Step-by-step explanation:

The question addresses the existence of a closed-form solution for the connectivity in terms of the radius of disks in a two-dimensional system with open boundary conditions, within the study of random geometric graphs (RGGs). Unfortunately, while a closed-form solution exists for RGGs with periodic boundary conditions, described by the equation κ = NVex = 4πNr², where Vex is the excluded volume of a disk, finding an exact closed-form solution for open boundary conditions has proven to be elusive.

Open boundary conditions lead to lower connectivity, indicated as κkopen < κk. Although numerical simulations can predict the connectivity for open boundaries, they do not provide a closed-form equation. The question also notes that the critical connectivity appears to be boundary condition-independent as the number of vertices N approaches infinity.

The reliance on numerical methods rather than an analytic formula makes it challenging to generate graphs for specific connectivity values directly. The lack of a closed-form expression remains an open problem in the mathematical study of two-dimensional systems and graph theory.