Laman graph

Laman graph

In graph theory, the Laman graphs are a family of sparse graphs describing the minimally rigid systems of rods and joints in the plane. Formally, a Laman graph is a graph on "n" vertices such that, for all "k", every "k"-vertex subgraph has at most 2"k" −3 edges, and such that the whole graph has exactly 2"n" −3 edges. Laman graphs are named after Gerard Laman, of the University of Amsterdam, who in 1970 used them to characterize rigid planar structures. [citation|first=G.|last=Laman|title=On graphs and the rigidity of plane skeletal structures|journal=J. Engineering Mathematics|volume=4|year=1970|pages=331–340|doi=10.1007/BF01534980|id=MathSciNet|id=0269535.]

Laman graphs arise in rigidity theory: if one places the vertices of a Laman graph in the Euclidean plane, in general position, there will in general be no simultaneous motion of all the points, other than Euclidean congruences, that preserves the lengths of all the graph edges, and the Laman graphs are the minimal graphs with this property. Intuitively, each edge reduces the number of degrees of freedom in the system of points by one, so the 2"n" −3 edges in a Laman graph reduce the 2"n" degrees of freedom of the initial point placement to the three degrees of freedom that are sufficient to describe any Euclidean congruence. The condition that no subgraph have too many edges ensures that each edge contributes to reducing the overall number of degrees of freedom, and is not wasted within a subgraph that is already itself rigid due to its other edges.

Every pointed pseudotriangulation is a Laman graph, and every planar Laman graph can be realized as a pointed pseudotriangulation. [cite journal
author = Haas, Ruth; Orden, David; Rote, Günter; Santos, Francisco; Servatius, Brigitte; Servatius, Herman; Souvaine, Diane; Streinu, Ileana; Whiteley, Walter
title = Planar minimally rigid graphs and pseudo-triangulations
journal = Computational Geometry Theory and Applications
volume = 31
issue = 1–2
pages = 31–61
year = 2005
doi = 10.1016/j.comgeo.2004.07.003
id = MathSciNet | id = 2131802] However, there are Laman graphs that are not planar, such as the complete bipartite graph "K"3,3.

References


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Gerard Laman — (born August 22, 1924), Dutch mathematician, worked on graph theory.Gerard Laman was born in Leiden, The Netherlands. He completed high school studies at the Leids Gymnasium in 1942. His study of Mathematics at Leiden University was delayed by a… …   Wikipedia

  • Dense graph — In mathematics, a dense graph is a graph in which the number of edges is close to the maximal number of edges. The opposite, a graph with only a few edges, is a sparse graph. The distinction between sparse and dense graphs is rather vague, and… …   Wikipedia

  • Pseudotriangle — In Euclidean plane geometry, a pseudotriangle is the simply connected subset of the plane that lies between any three mutually tangent convex sets. A pseudotriangulation is a partition of a region of the plane into pseudotriangles, and a pointed… …   Wikipedia

  • List of mathematics articles (L) — NOTOC L L (complexity) L BFGS L² cohomology L function L game L notation L system L theory L Analyse des Infiniment Petits pour l Intelligence des Lignes Courbes L Hôpital s rule L(R) La Géométrie Labeled graph Labelled enumeration theorem Lack… …   Wikipedia

  • Ламанов граф — В теории графов Ламановым графом с n вершинами называют такой граф G, что, во первых, для каждого k любой подграф графа G, содержащий k вершин, имеет не более, чем 2k −3 ребра и, во вторых, граф G имеет ровно 2n −3 ребра. Ламановы графы …   Википедия

  • Liste de théorèmes — par ordre alphabétique. Pour l établissement de l ordre alphabétique, il a été convenu ce qui suit : Si le nom du théorème comprend des noms de mathématiciens ou de physiciens, on se base sur le premier nom propre cité. Si le nom du théorème …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”