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]
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.
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.
If \(m < t\), output
False
(as the graph cannot even be generically \(d\)-rigid with so few edges), otherwise continue.Pick a framework with integer coordinates randomly chosen from 1 to \(N\).
Pick an equilibrium stress vector in a suitably random way. (If \(m = 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 \(n-d-1\) then return
True
, otherwise returnFalse
.
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
\(\{u,v\}\) is a separating pair in G, or
\(C(B,V_0)\) is globally 2-rigid,
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]