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, the relation \(k_{min}(G,d) \geq d+1\) holds.

References: [GHT10, Lem 1.11]

Definition 22

A graph \(G\) is said to have a minimal stress kernel in \(\RR^d\) if \(k_{min}(G,d) = d+1\).

References: [GHT10]

Theorem 7

Let \(G\) be a graph with \(d+2\) or more vertices. If \(G\) has a minimal stress kernel in \(\RR^d\), then all generic frameworks \((G,p)\) are globally \(d\)-rigid.

References: [Con05, Thm 1.3], [GHT10, Thm 1.13]

The converse of this theorem is the following one:

Theorem 8

Let \(G\) be a graph with \(d+2\) or more vertices. If \(G\) does not have a minimal stress kernel in \(\RR^d\), then any \(d\)-dimensional generic framework \((G,p)\) is not globally \(d\)-rigid.

References: [GHT10, Thm 1.14]

The following randomized algorithm from [GHT10] checks for global \(d\)-rigidity.

Algorithm 1

Input: A natural number \(d\) and a graph \(G = (V, E)\) with at least \(d + 2\) vertices

Output: True or False, whether or not \(G\) is globally \(d\)-rigid

Let \(n = |V|\) and \(m = |E|\), let \(t = n\cdot d - \binom{d+1}{2}\), and \(N = A \cdot n\cdot \binom{n}{2} +2\), where \(A\) is some constant.

  1. If \(m < t\), output False (as the graph cannot even be generically \(d\)-rigid with so few edges), otherwise continue.

  2. Pick a framework with integer coordinates randomly chosen from 1 to \(N\).

  3. Pick an equilibrium stress vector in a suitably random way. (If \(m = t\), there are no stresses, so we consider the zero vector.)

  4. Consider the corresponding equilibrium stress matrix and compute its rank.

  5. If the rank is \(n-d-1\) then return True, otherwise return False.

PyRigi: is_globally_rigid()

References: [GHT10, Alg 5.3]

The above algorithm may give false negatives as the following theorem tells.

Theorem 9

The randomized algorithm for checking global d-rigidity never returns a false positive answer, and returns a false negative answer with probability bounded above by \(nm/N\), where \(n\) is the number of vertices, \(m\) is the number of edges and \(N\) is an arbitrarily large integer. Given a number \(A\), we chose \(N \geq A\cdot nm + 2\) so that the probability of getting a false negative is less than \(1/A\). In particular, checking for generic global \(d\)-rigidity is in \(RP\), i.e., the class of randomized polynomial time algorithms.

PyRigi: is_globally_rigid()

References: [GHT10, Thm 5.10]

Definition 23 (globally linked in a framework)

We say that a pair of vertices \(\{u,v\}\) is globally linked in a \(d\)-dimensional framework \((G,p)\) if for every equivalent \(d\)-dimensional framework \((G,q)\) we have \(||p(u)-p(v)|| = ||q(u)-q(v)||\). This is not a generic property.

References: [JV24]

Definition 24 (globally linked in a graph)

A pair of vertices \(\{u,v\}\) is globally \(d\)-linked in \(G\) if it is globally linked in all \(d\)-dimensional generic frameworks \((G,p)\).

A pair \(\{u,v\}\) is weakly globally \(d\)-linked in \(G\) if there exists a \(d\)-dimensional generic framework \((G,p)\) in which \(\{u,v\}\) is globally linked.

References: [JV24]

Theorem 10

A graph \(G\) is globally d-rigid if and only if every pair of vertices is weakly globally d-linked in \(G\).

References: [JV24, Lem 3.2]

Corollary 1

Given a \(d\)-rigid but not globally \(d\)-rigid graph \(G\), there exists at least one pair of vertices of \(G\) that are not weakly globally d-linked in \(G\).

Definition 25 (linked pair)

A pair of vertices \(\{u,v\}\) of \(G\) is linked in a \(d\)-dimensional framework \((G,p)\) (or \(uv\) is an implied edge of \((G,p)\)) if the set of distances \(\{ \|q(u) - q(v) \| : (G,q) \text{ is equivalent to } (G,p) \}\) is finite.

A pair of vertices \(\{u,v\}\) of \(G\) is \(d\)-linked if it is linked in all \(d\)-dimensional generic frameworks \((G,p)\).

References: see [Jor16, Sec 3.6.4] for a different but equivalent definition

Lemma 2

A pair \(\{u, v\}\) is 2-linked in \(G\) if and only if there exists a 2-rigid component of \(G\) containing \(u\) and \(v\).

References: compare [Jor16, Sec 3.6.4]

Note that Lemma 2 does not hold in higher dimensions.

Lemma 3

A pair \(\{u, v\}\) of vertices is non-adjacent and 2-linked in \(G\) if and only if there exists some subgraph \(G_0 = (V_0,E_0)\) of \(G\) with \(u,v\in V_0\) such that \(G_0+uv\) is an \(\mathcal{R}_2\)-circuit.

References: [JV24, Sec 5.1]

Definition 26 (augmented graph)

Given a graph \(G\), its augmented graph is the graph obtained from \(G\) by adding an edge between every separating pair of \(G\).

Definition 27 (cleaving operation)

Let \(G=(V,E)\) be a 2-connected graph and \(u,v\in V\) be such that \(\{u,v\}\) is a separating pair of \(G\). Let \(C\) be a connected component of \(G-\{u,v\}\) and let \(H\) be the subgraph of \(G\) induced by \(V(C) \cup \{u,v\}\). We say that \(H + uv\) is obtained from \(G\) by a cleaving operation along \(\{u,v\}\).

Lemma 4

Let \(G\) be a 2-connected graph and let \(\{u,v\}\) be a non-adjacent vertex pair in \(G\) with local connectivity \(\kappa_G(u,v) \geq 3\). Then either \(\{u,v\}\) is a separating pair in \(G\) or there is a unique 3-connected component \(B\) of the augmented graph of \(G\) such that \(\{u,v\} \subset V(B)\). In the latter case the subgraph \(B\) can be obtained from \(G\) by a sequence of cleaving operations. Furthermore, \(uv \notin E(B)\) and if the pair \(\{u,v\}\) is 2-linked in \(G\) then it is also 2-linked in \(B\).

References: [JV24, Lem 5.7]

Definition 28 (3-block)

Let \(G\) be a 2-connected graph and let \(\{u,v\}\) be a non-adjacent vertex pair in \(G\) which is not a separating pair. The unique 3-connected component \(B\) of the augmented graph of \(G\) such that \(\{u,v\}\subset V(B)\) is called the 3-block of \(\{u,v\}\) in \(G\).

References: [JV24]

Theorem 11

Let \(G\) be a 2-connected graph and let \(\{u,v\}\) be a non-adjacent 2-linked pair of vertices with local connectivity \(\kappa_G(u,v) \geq 3\). Then \(\{u,v\}\) is weakly globally 2-linked in \(G\) if and only if either

where \(B\) is the 3-block of \(\{u,v\}\) in \(G\), \(B_0 = (V_0,E_0)\) is a subgraph of \(B\) with \(u,v \in V_0\) such that \(B_0 + uv\) is an \(\mathcal{R}_2\)-circuit, and \(C(B, V_0)\) is the graph obtained as follows.

Let \(V_1,\dots, V_r\) be the vertex sets of the connected components of \(B-V_0\). Delete from \(B\) the vertex sets \(V_i\) for \(1\leq i\leq r\) and add the edges \(xy\) for all pairs \(x,y \in N_B(V_i)\) for \(1\leq i\leq r\). Here \(N_B(V_i)\) denotes the set of nodes of \(B-V_i\) that are connected by an edge to some vertex of \(V_i\). The resulting graph is \(C(B, V_0)\).

PyRigi: is_weakly_globally_linked()

References: [JV24, Thm 5.8]