Rigidity

Problems in this category:

• Achieve global rigidity by pinning nodes
• Destroying rigidity
• Generic global rigidity in three dimensions
• Generic rigidity in three dimensions

Introduction

For the basic definitions on rigidity of frameworks and graphs, see the page Rigid graph, or see the survey of Whiteley for a detailed overview.

Given a d-dimensional framework (G,p), the associated rigidity matrix R(G,p) defines 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.

A framework (G,p) is infinitesimally rigid in dimension [math]d[/math] if it has no nontrivial infinitesimal motions. Equivalently, the nullspace of the rigidity matrix is the vector space of trivial infinitesimal motions, or the rank of the matrix is [math]r(R(G,p))=d|V|-{d+1 \choose 2}[/math] assuming that [math]|V|\geq d+1[/math] holds.

It can be shown that infinitesimal rigidity implies rigidity in any dimension. There are examples even in 2-dimensional space for rigid frameworks that are not infinitesimally rigid. However, the reason for this is that the framework is not generic: the two notions coincide for generic realizations. This makes it possible to study rigidity problems as matrix or matroid problems.

Rigidity matroid

Being a question about the rank of a matrix, infinitesimal rigidity can be described in matroid terms. A graph is rigid in d-dimensional space if for a generic realization, the matroid defined by the rows of [math]R(G,p)[/math] (the 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 . One important open question in the area is to describe the properties of the rigidity matroid in higher dimensions.

2-dimensional rigidity

Although the rigidity matroid is well understood in 2-dimensional space, there are some fundamental questions that remain open. One is the computation of the co-girth of the matroid:

Let G be a graph that is rigid in two-dimensional space. Can we determine in polynomial time the minimum number of edges whose deletion from G results in a graph which is not rigid?

Global rigidity in 2-dimensional space can also be characterized with the help of the rigidity matroid: a graph is globally rigid if and only if it is 3-connected and redundantly rigid . This characterization answers many questions about global rigidity; one that remains open is how to achieve global rigidity by pinning nodes:

Given a graph [math]G(V,E)[/math], find a minimum cardinality set [math]S \subset V[/math] of nodes such that adding a complete graph on [math]S[/math] renders the graph [math]G+K_S[/math] globally rigid in 2-dimensional space.

Rigidity in 3-dimensional space

New difficulties arise in 3D, because the rigidity matroid is not well characterized. In fact, it is open whether we can decide generic rigidity in three dimensions or generic global rigidity in three dimensions in polynomial time, although randomized polynomial algorithms exist; see Matrices with indeterminates for a broader discussion of this topic.