Source-linked AI summary
Characterizing Generic Global Rigidity
Steven J. Gortler, Alexander D. Healy, Dylan P. Thurston
TL;DR
The paper asks which graphs have globally rigid generic frameworks and resolves this by proving necessity of Connelly’s stress-kernel condition. It characterizes global rigidity through stress and Gauss-map formulations, gives a randomized polynomial-time test, and establishes higher-dimensional flexibility when generic global rigidity fails.
Problem
The paper seeks to characterize which underlying graphs make a generic framework globally rigid, motivated by distance-based geometric inference in chemistry and sensor networks.
Method
The paper proves the converse of Connelly’s sufficient condition and studies the length-squared map, shared stress kernel, and Gauss map to obtain alternate characterizations.
Results
A generic framework is globally rigid if and only if its graph has a minimal stress kernel; the condition is checkable by a polynomial-time randomized algorithm, and failure implies a constant-edge-length connection to an incongruent framework in E^(d+1).
Takeaways & Limitations
Generic global rigidity can be treated as a graph property and tested efficiently, while non-global rigidity in E^d yields flexibility one dimension higher.
Takeaways & Limitations
The stronger non-generic strengthening does not hold because global rigidity can fail at non-generic points, for example through transverse self-intersections of the length-squared image.
Abstract
from arXiv · showhide
A d-dimensional framework is a graph and a map from its vertices to E^d. Such a framework is globally rigid if it is the only framework in E^d with the same graph and edge lengths, up to rigid motions. For which underlying graphs is a generic framework globally rigid? We answer this question by proving a conjecture by Connelly, that his sufficient condition is also necessary: a generic framework is globally rigid if and only if it has a stress matrix with kernel of dimension d+1, the minimum possible. An alternate version of the condition comes from considering the geometry of the length-squared mapping l: the graph is generically locally rigid iff the rank of l is maximal, and it is generically globally rigid iff the rank of the Gauss map on the image of l is maximal. We also show that this condition is efficiently checkable with a randomized algorithm, and prove that if a graph is not generically globally rigid then it is flexible one dimension higher.
1. Introduction
The paper characterizes generic global rigidity as a graph property by proving Connelly’s sufficient stress-kernel condition is necessary. It also gives alternate geometric formulations, an efficient randomized test, and a higher-dimensional flexibility result.
- Main characterization: Global rigidity is characterized for generic frameworks in d-dimensional Euclidean space through a condition depending only on the graph and dimension.This makes generic global rigidity a property of the underlying graph rather than of a particular generic realization.
- Main characterization: A generic framework is not globally rigid when its graph with d + 2 or more vertices lacks a minimal stress kernel in E^d.This is the converse completing Connelly’s characterization.
- Genericity: Generic global rigidity is itself generic: either all generic frameworks of a graph are globally rigid, or none are.The same generic-property principle is established for local rigidity through maximal rank of the length-squared map.
- Algorithmic consequence: A polynomial-time randomized algorithm checks generic global rigidity in E^d.The algorithm follows from the paper’s characterization results.
- Higher-dimensional consequence: If a graph is not generically globally rigid in E^d, every generic framework can connect to an incongruent framework in E^(d+1) through a constant-edge-length path.The result establishes flexibility one dimension higher.
- Alternate formulations: The paper relates generic global rigidity to the shared stress kernel and maximal rank of the Gauss map on the image of the length-squared mapping.These provide alternate characterizations alongside the stress-kernel criterion.
2. Proof of main theorem
The proof converts failure of a minimal stress kernel into a map whose mod-two degree is zero, forcing multiple incongruent frameworks with identical edge lengths. It connects this construction to measurement-set geometry through stress spaces, contact loci, and flat ranges.
- Proof strategy: The proof constructs a map whose preimages correspond to incongruent frameworks sharing the same edge lengths, then proves its mod-two degree is zero.A degree of zero means regular values have an even number of preimages, enabling the necessity argument.
- Proof strategy: The length-squared map is factored through configurations modulo Euclidean motions and onto the measurement set, whose dimension matches the quotient under local rigidity.The measurement set is the image of the length-squared map and is an irreducible semi-algebraic set.
- Stress construction: A generic equilibrium stress defines a space A(Ω) of frameworks satisfying the stress, and global flexes must lie in this space.The proof uses A(Ω)/Eucl(d) as the domain of the map.
- Stress construction: For a generic stress, the image B(Ω) is a flat contact locus contained in a linear space L(Ω) of the same dimension, which serves as the map’s range.The stress-space and contact-locus descriptions connect the framework construction to the dual geometry of the measurement set.
- Conclusion: When a generically locally rigid graph lacks minimal stress kernel in E^d, the associated map has mod-two degree zero; since [ρ] is one preimage, another incongruent framework exists.The regular-value property of ℓ(ρ) supports the conclusion that the second preimage corresponds to a framework with the same edge lengths.
3. Examples
The examples show how stress spaces and affine stress-satisfier spaces expose failures of generic global rigidity, including local flexibility, lack of connectivity, and bipartite counterexamples.
- 3.1. Locally flexible graphs: Locally flexible graphs can have an affine stress-satisfier space containing all embeddings, so its dimension alone need not distinguish global rigidity.For the tripod graph in E2, the only equilibrium stress is zero and A(Ω) contains all embeddings, while L(Ω) is three-dimensional.
- 3.2. Not redundantly rigid.: Deleting an edge that destroys generic local rigidity leaves the equilibrium stress spaces unchanged, because every stress has zero on that edge.The resulting affine space contains affine transforms of frameworks preserving every original edge length except the deleted one.
- 3.3. Graphs that are not (d + 1)-connected.: A separating set of d vertices permits two affine transforms that agree on the interface, including folding one graph half across the interface.The induced interface forces lie in the interface plane, so affinely squashing or reflecting one half preserves the stress constraints.
- 3.4. Bipartite graphs.: For K5,5 in E3, the stress matrix has rank 2 and an 8-dimensional kernel, while L(Ω) is 18-dimensional.The two bipartition classes may undergo separate affine transforms, and the resulting framework is redundantly rigid but not generically globally rigid.
- 3.4. Bipartite graphs.: More generally, these bipartite examples satisfy kmin = |n −m| + 2(d + 1) > d + 1, so they fail the minimal stress-kernel condition.Thus, as Connelly stated, they are not generically globally rigid despite satisfying the relevant Hendrickson conditions.
- 3.5. Generically globally rigid graphs.: When Connelly’s condition does hold, the stress kernel has dimension d + 1 and A(Ω) reduces to Aff(ρ), contrasting with the bipartite examples.The edge vectors are independent because the framework’s edges do not lie on a conic at infinity, and the length map is injective on Aff(ρ)/Eucl(d).
4. Shared stress kernels and the rank of the Gauss map
The shared stress kernel provides an alternate characterization of generic global rigidity, equivalent to maximal rank of the Gauss map on the measurement set. Theorem 4.4 identifies generic global rigidity exactly with shared stress nullity d+1, the minimum possible dimension.
- Shared stress kernels: The shared stress kernel K(ρ) is the intersection of all equilibrium stress kernels and represents one-dimensional frameworks satisfying every stress.Its generic dimension defines the shared stress nullity ksh(Γ, d), which is independent of the chosen generic framework.
- Shared stress kernels: Although kmin and ksh can differ, either nullity can be used in a global-rigidity test, and kmin = v − d − 1 implies ksh = v − d − 1.The example K7,8 in E4 has kmin = 11 and ksh = 10.
- Global-rigidity criterion: A graph with d + 2 or more vertices is generically globally rigid in E^d if and only if ksh(Γ, d) = d + 1.The proof places any equivalent framework in the shared-stress solution space, then uses the absence of a conic at infinity to conclude congruence.
- Gauss-map rank: Generic local rigidity corresponds to maximal rank of the length-squared map ℓ, while generic global rigidity corresponds to maximal Gauss rank.Both properties are characterized through local behavior of the measurement set, despite global rigidity being a global uniqueness property.
- Gauss-map rank: The Gauss maps G and G ◦ ℓ both have rank vd − kshd, linking shared stress nullity directly to the dimension of the Gauss-map image.The fiber dimension calculation gives dim A(ρ) = dim C^d(Γ) − rank(G ◦ ℓ).
- Equivalent formulations: Minimal stress kernel, maximal Gauss rank, and generic global rigidity are equivalent conditions for a graph in E^d.The maximal Gauss rank is vd − (d + 1)d.
5. Complexity of the algorithm
The paper develops deterministic and randomized procedures for testing generic global rigidity through rigidity-matrix and stress-matrix ranks. The randomized test runs in polynomial time with one-sided error, placing the problem in RP.
- Deterministic algorithm: The deterministic global check symbolically computes the rigidity-matrix rank and the kernel of its transpose, accepting when the resulting stress rank equals s.Although correct, it may be very slow because symbolic polynomial expressions can grow rapidly.
- Randomized algorithm: The randomized global check samples integer-coordinate frameworks, constructs a random equilibrium stress, and accepts when its stress matrix has rank s.It first rejects graphs with too few edges or unfavorable rank conditions.
- Error guarantees: Schwartz-Zippel bounds the probability that random sampling misses the generic rank: for local rigidity, a false “no” occurs with probability below t/N.Choosing N > 2t makes the false-negative probability less than one half, while false “yes” answers never occur.
- Complexity: The rank computations run in time polynomial in log N and matrix size, so generic global-rigidity testing is in RP.The algorithms have one-sided error: they always reject non-generic-global-rigidity instances and accept positive instances with probability at least one half.
- Error guarantees: The global randomized algorithm never returns a false “yes” and returns a false “no” with probability at most ve/N.Taking N > 2ve makes the false-negative probability less than one half.
- Complexity: Exact modular linear algebra can preserve the one-sided guarantee when primes are sampled from a sufficiently large set above N.For global rigidity, the required set size and coordinate bound exceed 4ve, with primes needed only up to about 8ve ln(4ve).
6. Smooth higher-dimensional flexes
The paper constructs a smooth constant-length flex in E^{d+1} by analyzing fibers of a lifted length-squared map and quotienting by Euclidean motions. Under genericity and local rigidity assumptions, the relevant fiber is smooth, and connectedness yields a second incongruent d-dimensional framework.
- The higher-dimensional flex: A generic non-globally-rigid framework can be connected to an incongruent framework by a smooth constant-edge-length path in E^{d+1}.Thus one extra dimension suffices, although reaching every alternative framework remains open.
- Construction: The proof restricts the search to (d+1)-dimensional frameworks satisfying a suitably generic equilibrium stress.The lifted stress-satisfier space is linear, and the flex remains within the connected component containing the original embedded framework.
- Smoothness: For generic data, the edge-length fiber is a smooth manifold because the original edge lengths are a regular value of the lifted length-squared map.Genericity of the edge lengths inside the relevant algebraic image enables the use of Sard’s theorem and the implicit function theorem.
- Quotient geometry: When the graph is generically locally rigid and the stress-kernel dimension satisfies k > d+1, quotienting the fiber by Euclidean motions produces a smooth stratified space of dimension k.Its singularities have codimension at least 2, so they do not obstruct the subsequent connectivity argument.
- Conclusion: The quotient map has another preimage of the zero point, corresponding to a second incongruent framework in E^d; connectedness then supplies the desired smooth path in E^{d+1}.The zero point is regular, and the relevant fiber contains an even number of points, including the original framework and another one.