Changes
==Problems in this category:==
==Introduction==
For the basic definitions on rigidity of frameworks and graphs, see the page [[Rigid graph]], or see the survey of Whiteley <ref name="Wi2"/> for more information.
For a framework ''(G,p)'', we introduce the ''d''-dimensional [[rigidity matrix]] ''R(G,p)'' to describe infinitesimal rigidity. An '''infinitesimal motion''' of a framework is an assignment <math>s:V \rightarrow \mathbb{R}^d</math> of vectors to the nodes such that the corresponding motion preserves edge lengths. More precisely, <math>( p(u)-p(v)) ( s(u)-s(v)) =0</math> for every edge ''uv'', that is, each edge is orthogonal to the difference of the infinitesimal motions of its endpoints. This can be written as <math>R(G,p)s=0</math>. Some trivial infinitesimal motions can be derived from isometries of <math>\mathbb{R}^d</math> that do not change orientation. These form a vector space of dimension <math>d+1 \choose 2</math> with <math>d</math> independent shifts and <math>d-1 \choose 2</math> independent rotations.
Being a question about the rank of a matrix, infinitesimal rigidity can be described in matroid terms. A graph is [[Rigid graph|rigid]] in ''d'' dimensions if for a generic realization, the matroid defined by the rows of <math>R(G,p)</math> (the [[Rigidity matrix|rigidity matroid]]) has rank at least <math>\min \left\{ {|V|\choose 2} , d|V|-{d+1 \choose 2} \right\}</math>.
In dimension 2 this is a [[count matroid]] <ref>G. Laman, ''On graphs and rigidity of plane skeletal structures'', J. Eng. Math. 4 (1970), 331-340. [http:name ="La"//dx.doi.org/10.1007/BF01534980 DOI link].</ref>. One important open question in the area is to describe the properties of the rigidity matroid in higher dimensions.
==Rigidity in 2 dimensions==
{{IncludeOpenProblem|Destroying rigidity}}
Global rigidity in 2 dimensions is can also be characterized using with the help of the rigidity matroid: a graph is globally rigid if and only if it is 3-connected and [[Rigid graph|redundantly rigid]] <ref>B. Jackson, T. Jordán, ''Connected rigidity matroids and unique realizations of graphs'', [http:name="JaJo"//dx.doi.org/10.1016/j.jctb.2004.11.002 DOI link], [http://www.cs.elte.hu/egres/tr/egres-02-12.pdf EGRES Technical Report].</ref>. This characterization answers many questions about global rigidity; one that remains open is how to [[achieve global rigidity by pinning nodes]]:
{{IncludeOpenProblem|Achieve global rigidity by pinning nodes}}
==References==
<references>
<ref name="Wi2">W. Whiteley, ''Rigidity and scene analysis'', in: Handbook of Discrete and Computational Geometry, [http://www.utdallas.edu/~besp/rigid/Whiteley_Chapter.pdf pdf link].</ref>
<ref name ="La">G. Laman, ''On graphs and rigidity of plane skeletal structures'', J. Eng. Math. 4 (1970), 331-340. [http://dx.doi.org/10.1007/BF01534980 DOI link].</ref>
<ref name="JaJo">B. Jackson, T. Jordán, ''Connected rigidity matroids and unique realizations of graphs'', [http://dx.doi.org/10.1016/j.jctb.2004.11.002 DOI link], [http://www.cs.elte.hu/egres/tr/egres-02-12.pdf EGRES Technical Report].</ref>
<references/>
[[Category: Surveys]]
