Random geometric graph

Random geometric graph

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
# Placing vertices at random uniformly and independently on the region
# 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".


* Penrose, Mathew: "Random Geometric Graphs" (Oxford Studies in Probability, 5), 2003.

Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Graph theory — In mathematics and computer science, graph theory is the study of graphs : mathematical structures used to model pairwise relations between objects from a certain collection. A graph in this context refers to a collection of vertices or nodes and …   Wikipedia

  • Geometric group theory — is an area in mathematics devoted to the study of finitely generated groups via exploring the connections between algebraic properties of such groups and topological and geometric properties of spaces on which these groups act (that is, when the… …   Wikipedia

  • Random walk — A random walk, sometimes denoted RW, is a mathematical formalization of a trajectory that consists of taking successive random steps. The results of random walk analysis have been applied to computer science, physics, ecology, economics and a… …   Wikipedia

  • Unit disk graph — In geometric graph theory, a unit disk graph is the intersection graph of a family of unit circles in the Euclidean plane. That is, we form a vertex for each circle, and connect two vertices by an edge whenever the corresponding circles cross… …   Wikipedia

  • Crossing number (graph theory) — A drawing of the Heawood graph with three crossings. This is the minimum number of crossings among all drawings of this graph, so the graph has crossing number cr(G) = 3. In graph theory, the crossing number cr(G) of a graph G is the… …   Wikipedia

  • List of mathematics articles (R) — NOTOC R R. A. Fisher Lectureship Rabdology Rabin automaton Rabin signature algorithm Rabinovich Fabrikant equations Rabinowitsch trick Racah polynomials Racah W coefficient Racetrack (game) Racks and quandles Radar chart Rademacher complexity… …   Wikipedia

  • List of mathematics articles (G) — NOTOC G G₂ G delta space G networks Gδ set G structure G test G127 G2 manifold G2 structure Gabor atom Gabor filter Gabor transform Gabor Wigner transform Gabow s algorithm Gabriel graph Gabriel s Horn Gain graph Gain group Galerkin method… …   Wikipedia

  • Hereditary property — In mathematics, a hereditary property is a property of an object, that inherits to all its subobjects, where the term subobject depends on the context. These properties are particularly considered in topology and graph theory. Contents 1 In… …   Wikipedia

  • Constellation model — The constellation model is a probabilistic, generative model for category level object recognition in computer vision. Like other part based models, the constellation model attempts to represent an object class by a set of N parts under mutual… …   Wikipedia

  • Logarithm — The graph of the logarithm to base 2 crosses the x axis (horizontal axis) at 1 and passes through the points with coordinates (2, 1), (4, 2), and (8, 3) …   Wikipedia