Global Rigidity¶

Definition 20

A graph $G = (V,E)$ is called globally $d$-rigid, if for every generic $d$-dimensional framework $(G,p)$, all $d$-dimensional frameworks $(G,p')$ equivalent to $(G,p)$ are congruent to $(G,p)$.

References: [JJ05]

is_globally_rigid()

Theorem 5

A graph $G$ is globally $2$-rigid if and only if it either is a complete graph on at most three vertices or it is $3$-connected and redundantly rigid.

References: [JJ05, Thm 7.1]

Theorem 6

Let $G$ be a $6$-connected 2-rigid graph. Then $G$ is globally $2$-rigid.

References: [JJ05, Thm 7.2]

Definition 21

Let $G$ be a graph, if $\Omega$ is an equilibrium stress matrix, its kernel is called stress kernel; we denote it by $K(\Omega)$ and its dimension by $k(\Omega)$. We denote by $k_{min}(G,d)$ the minimal value of $k(\Omega)$ as $\Omega$ ranges over all equilibrium stress matrices of all generic $d$-dimensional frameworks of $G$.

References: [GHT10]

Lemma 1

For frameworks of a graph $G$ with at least $d+1$ vertices, it holds $k_{min}(G,d) \geq d+1$.

References: [GHT10]

Definition 22

A graph $G$ has a minimal stress kernel in $\mathbb{R}^d$ if $k_{min}(G,d) = d+1$.

References: [GHT10]

Theorem 7

If a graph $G$ with $d+2$ or more vertices has a minimal stress kernel in $\mathbb{R}^d$, then all generic frameworks $p$ of $G$ are globally rigid.

References: [GHT10]

The converse of this theorem is the following one:

Theorem 8

If a graph $G$ with $d+2$ or more vertices does not have a minimal stress kernel in $\mathbb{R}^d$, then any generic framework $p$ of $G$ is not globally rigid.

References: [GHT10]

The method PyRigi: is_globally_rigid() uses the following randomized algorithm:

Let $d$ be the dimension for which we want to test whether the graph is globally $d$-rigid, $v$ be the number of vertices, $e$ be the number of edges, $t = v\cdot d - \binom{d+1}{2}$ and $N = A\cdot v\cdot \binom{v}{2} +2$, where $A$ is a constant. To check if a graph with at least $d + 2$ vertices is generically globally rigid in $\RR^d$, proceed as follows:

If $e < t$, output False (as the graph cannot even be generically locally rigid with so few edges), otherwise continue.
Pick a framework with integer coordinates randomly chosen from 1 to $N$.
Pick one equilibrium stress vector in a suitably random way. (If $e = t$, there are no stresses, so we consider the zero vector.)
Consider the corresponding equilibrium stress matrix and compute its rank.
If the rank is $v-d-1$, return True, otherwise return False .

Theorem 9

The randomized algorithm for checking global rigidity never returns a false True answer, and returns a false False answer with probability bounded above by $ve/N$, where $v$ is the number of vertices, $e$ is the number of edges and $N$ is an arbitrarily large integer. In this case, we chose $N \geq A\cdot ve + 2$ so that the probability of getting a false False is less than $1/A$. In particular, checking for generic global rigidity in $\mathbb{R}^d$ is in $RP$, i.e., the class of randomized polynomial time algorithms.

PyRigi: is_globally_rigid() References: [GHT10]