en>Loraof: /* Methods of Solution */ wikifying

2014-11-16T15:28:16Z

Methods of Solution: wikifying

217.172.21.210 at 15:43, 28 March 2010

2010-03-28T15:43:12Z

New page

[[File:Moser spindle pseudotriangulation.svg|thumb|240px|The [[Moser spindle]], a planar Laman graph drawn as a [[pseudotriangle|pointed pseudotriangulation]]]]
[[File:Biclique K 3 3.svg|thumb|150px|The [[complete bipartite graph]] ''K''3,3, a non-planar Laman graph]]
In [[graph theory]], the '''Laman graphs''' are a family of [[sparse graph]]s describing the minimally [[rigid system]]s 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.<ref>{{citation
| last = Laman | first = G.
| doi = 10.1007/BF01534980
| issue = 4
| journal = J. Engineering Mathematics
| mr = 0269535
| pages = 331–340
| title = On graphs and the rigidity of plane skeletal structures
| volume = 4
| year = 1970}}.</ref>

==Rigidity==
Laman graphs arise in [[rigidity theory (structural)|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 [[Congruence (geometry)|Euclidean congruences]], that preserves the lengths of all the graph edges. A graph is rigid in this sense if and only if it has a Laman subgraph that spans all of its vertices. Thus, the Laman graphs are exactly the minimally rigid graphs, and they form the bases of the two-dimensional [[rigidity matroid]]s.

If ''n'' points in the plane are given, then there are 2''n'' [[Degrees of freedom (engineering)|degrees of freedom]] in their placement (each point has two independent coordinates), but a rigid graph has only three degrees of freedom (the position of a single one of its vertices and the rotation of the remaining graph around that vertex).
Intuitively, adding an edge of fixed length to a graph reduces its number of degrees of freedom 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 of a rigid graph. However, not every graph with 2''n'' − 3 edges is rigid; the condition in the definition of a Laman graph that no subgraph can 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.

==Planarity==
A [[pseudotriangle|pointed pseudotriangulation]] is a [[planar straight-line graph|planar straight-line drawing]] of a graph, with the properties that the outer face is convex, that every bounded face is a [[pseudotriangle]], a polygon with only three convex vertices, and that the edges incident to every vertex span an angle of less than 180 degrees. The graphs that can be drawn as pointed pseudotriangulations are exactly the [[planar graph|planar]] Laman graphs.<ref>{{citation
| last1 = Haas | first1 = Ruth
| last2 = Orden | first2 = David
| last3 = Rote | first3 = Günter
| last4 = Santos | first4 = Francisco
| last5 = Servatius | first5 = Brigitte
| last6 = Servatius | first6 = Herman
| last7 = Souvaine | first7 = Diane | author7-link = Diane Souvaine
| last8 = Streinu | first8 = Ileana | author8-link = Ileana Streinu
| last9 = Whiteley | first9 = Walter
| doi = 10.1016/j.comgeo.2004.07.003
| issue = 1–2
| journal = Computational Geometry Theory and Applications
| mr = 2131802
| pages = 31–61
| title = Planar minimally rigid graphs and pseudo-triangulations
| volume = 31
| year = 2005}}.</ref> However, Laman graphs have planar embeddings that are not pseudotriangulations, and there are Laman graphs that are not planar, such as the [[utility graph]] ''K''3,3.

==Sparsity==
{{harvtxt|Streinu|Theran|2008}} define a graph as being <math>(k,l)</math>-sparse if every nonempty subgraph with <math>n</math> vertices has at most <math>kn-l</math> edges, and <math>(k,l)</math>-tight if it is <math>(k,l)</math>-sparse and has exactly <math>kn-l</math> edges. Thus, in their notation, the Laman graphs are exactly the (2,3)-tight graphs, and the subgraphs of the Laman graphs are exactly the (2,3)-sparse graphs. The same notation can be used to describe other important families of [[sparse graph]]s, including [[tree (graph theory)|trees]], [[pseudoforest]]s, and graphs of bounded [[arboricity]].<ref>{{citation|first1=I.|last1=Streinu|author1-link=Ileana Streinu|first2=L.|last2=Theran|year=2009|title=Sparse hypergraphs and pebble game algorithms|journal=[[European Journal of Combinatorics]]|volume=30|issue=8|pages=1944–1964|doi=10.1016/j.ejc.2008.12.018|arxiv=math/0703921 }}.</ref>

==Henneberg construction==
[[File:Henneberg construction of Moser spindle.svg|thumb|240px|Henneberg construction of the Moser spindle]]
Long before Laman's work, Lebrecht Henneberg characterized the two-dimensional minimally rigid graphs (that is, the Laman graphs) in a different way.<ref>{{citation
| last = Henneberg | first = L.
| location = Leipzig
| title = Die graphische Statik der starren Systeme
| year = 1911}}</ref> Henneberg showed that the minimally rigid graphs on two or more vertices are exactly the graphs that can be obtained, starting from a single edge, by a sequence of operations of the following two types:
#Add a new vertex to the graph, together with edges connecting it to two previously existing vertices.
#Subdivide an edge of the graph, and add an edge connecting the newly formed vertex to a third previously existing vertex.

A sequence of these operations that forms a given graph is known as a '''Henneberg construction''' of the graph.
For instance, the complete bipartite graph ''K''3,3 may be formed using the first operation to form a triangle and then applying the second operation to subdivide each edge of the triangle and connect each subdivision point with the opposite triangle vertex.

==References==
{{reflist}}

[[Category:Graph families]]
[[Category:Geometric graphs]]
[[Category:Mathematics of rigidity]]

Quadratic eigenvalue problem - Revision history

en>Loraof: /* Methods of Solution */ wikifying

217.172.21.210 at 15:43, 28 March 2010