Imagine I cover an arbitrarily large plane with randomly placed points at some density $\rho$ s.t. the number of points in any randomly sampled area $A$ (of arbitrary shape and size) is $\approx A*\rho$. We form a graph $G$ by connecting any pair of points with an edge if they are within unit length distance of one-another. Here, $G$ should be a sort of random unit disc graph.

Provided $\rho$, what is the probability that a randomly sampled vertex has degree $v = {0,1,2,...}$? If I select a set of points in a rectangular or circular area $A$ (which should introduce some bias), what is the expected probability distribution for the degree of vertices in the chosen set?

Also, I've been reading through the literature on percolation, but a heads up for a good paper relevant to the aforementioned graph $G$ in my question would be much appreciated!

  • 3
    $\begingroup$ If you use an arbitrarily large plane, or even better, a sphere or torus, shouldn't the degree of a vertex just be Poisson-distributed? I don't really understand the second paragraph, so maybe it could use some clarification. Colourings of random geometric graphs has been studied quite a lot, including by user RJK, who will probably come by in the near future with a more intelligent response. $\endgroup$ – Andrew D. King Apr 6 '13 at 18:10

The random placement of points you described is called Poisson point process (in the limit). The resulting graph is called Random Geometric Graph. Searches will yield a good crop of papers about these graphs.

The degree distribution (again, in the limit) is Poisson with parameter equal to the expected number of points in a disc of radius 1.


The degree of each vertex will be simply the number of points lying in a disc (sphere) around each point. For N uniformly distributed points, this number is a random variable drawn from the binomial distribution with the probability, p, being the area fraction of the disc relative to the window (thus, why this is called a Binomial process). In the limit of large N and constant number intensity, N/A, it is Poisson distributed with rate (N/A)pi r^2.

And as far as papers, there is an entire field of research on Random Geometric Graphs, but a good introduction would be the 2003 book by Penrose (aptly called Random Geometric Graphs), or you can look at this http://www.math.jyu.fi/research/pspdf/385.pdf.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.