# The probability distribution for vertex degree in a unit disc graph generated from random points on a plane

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!

• 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. 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.