Rigidity Theory

Here we list the very basic definitions used in Rigidity Theory. For further topics, see the links below.

Definition 1 (Realization)

Let \(G=(V,E)\) be a simple graph (i.e. no multi edges and no loops) and \(d\in\NN\). A \(d\)-dimensional realization of \(G\) is a map \(p\colon V\rightarrow \RR^d\). For convenience, for \(v \in V\) we may denote \(p(v)\) by \(p_v\).

The realization \(p\) is quasi-injective if \(p(u)\neq p(v)\) for every edge \(uv\in E\).

PyRigi: is_injective() is_quasi_injective()

Definition 2 (Framework)

Let \(G\) be a graph and let \(p\) be a \(d\)-dimensional realization of \(G\). The pair \((G, p)\) is a called a \(d\)-dimensional framework.

PyRigi: Framework graph() realization()

Definition 3 (Equivalent and congruent frameworks)

Two \(d\)-dimensional frameworks \((G, p)\) and \((G, p')\) with \(G = (V, E)\) are called equivalent if

\[\begin{equation*} \left\| p_u - p_v \right\| = \left\| p'_u - p'_v \right\| \quad \text{ for all } uv \in E \,. \end{equation*}\]

Two \(d\)-dimensional frameworks \((G, p)\) and \((G, p')\) with \(G = (V, E)\) are called congruent if

\[\begin{equation*} \left\| p_u - p_v \right\| = \left\| p'_u - p'_v \right\| \quad \text{ for all } u, v \in V \,. \end{equation*}\]

Definition 4 (Continuous flexes)

Let \((G, p)\) be a \(d\)-dimensional framework with \(G = (V, E)\). A continuous flex is a continuous map \(\alpha \colon [0, 1] \rightarrow (\RR^{d})^V\) such that

  • \(\alpha(0) = p\);

  • \((G, p)\) and \((G, \alpha(t))\) are equivalent for every \(t \in [0,1]\).

A continuous flex is called trivial if \((G, p)\) and \((G, \alpha(t))\) are congruent for every \(t \in [0,1]\).

Definition 5 (Continuously rigid frameworks)

A framework \((G, p)\) is called continuously rigid (from now on, simply rigid) if each of its continuous flexes is trivial. A framework \((G, p)\) is called flexible if it is not rigid.

Further topics