Random geometric graph

From Wikipedia, the free encyclopedia

In graph theory, a random geometric graph is a random undirected graph drawn on a bounded region, eg. the unit torus [0, 1)2. It is generated by

  1. Placing vertices at random uniformly and independently on the region
  2. Connecting two vertices, u, v if and only if the distance between them is at most a threshold r, ie. d (u, v) ≤ r.

Several probabilistic results are known about the number of components in the graph as a function of the threshold r and the number of vertices n.

[edit] References

  • Penrose, Mathew: Random Geometric Graphs (Oxford Studies in Probability, 5), 2003.
This combinatorics-related article is a stub. You can help Wikipedia by expanding it.