deterministic algorithmequilibrium stress matrixGauss mapgeneric frameworkgeneric local rigidityrandomized algorithm
Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62) Distance geometry (51K99) Rigidity and flexibility of structures (aspects of discrete geometry) (52C25) Differential geometric aspects in kinematics (53A17) Relations of low-dimensional topology with graph theory (57M15) Embeddings and immersions in PL-topology (57Q35) Statics (70C99) Rods (beams, columns, shafts, arches, rings, etc.) (74K10)
Abstract: 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.
Recommendations
Cited in
(only showing first 100 items - show all)- A proof of Connelly's conjecture on 3-connected circuits of the rigidity matroid.
- Algorithms for detecting dependencies and rigid subsystems for CAD
- Equivalent realisations of a rigid graph
- Recent results on assigned and unassigned distance geometry with applications to protein molecules and nanostructures
- On stress matrices of \((d + 1)\)-lateration frameworks in general position
- The rigidity of infinite graphs
- A note on generic rigidity of graphs in higher dimension
- Graph reconstruction from unlabeled edge lengths
- On the global rigidity of tensegrity graphs
- Spectral conditions for graph rigidity in the Euclidean plane
- Bearing-only distributed localization: a unified barycentric approach
- Sufficient conditions for the global rigidity of periodic graphs
- \(K_{5, 5}\) is fully reconstructible in \(\mathbb{C}^3\)
- Global rigidity of 2-dimensional direction-length frameworks with connected rigidity matroids
- Minimally globally rigid graphs
- A sufficient connectivity condition for rigidity and global rigidity of linearly constrained frameworks in \(\mathbb{R}^2\)
- Globally rigid powers of graphs
- An extension of the angular synchronization problem to the heterogeneous setting
- Generically globally rigid graphs have generic universally rigid frameworks
- On the maximal number of real embeddings of minimally rigid graphs in \(\mathbb{R}^2,\mathbb{R}^3\) and \(S^2\)
- Fully distributed affine formation control of general linear systems with uncertainty
- Global rigidity of periodic graphs under fixed-lattice representations
- On Graver's conjecture concerning the rigidity problem of graphs
- Global rigidity of generic frameworks on the cylinder
- Sufficient conditions for the global rigidity of graphs
- Iterative universal rigidity
- On dimensional rigidity of bar-and-joint frameworks
- Characterizing graphs with convex and connected Cayley configuration spaces
- Global rigidity of triangulations with braces
- Generic global rigidity
- Globally linked pairs of vertices in equivalent realizations of graphs
- Global rigidity of (quasi-)injective frameworks on the line
- The unassigned distance geometry problem
- Generalised rigid body motions in non-Euclidean planes with applications to global rigidity
- Vertex splitting, coincident realisations, and global rigidity of braced triangulations
- Characterizing the universal rigidity of generic tensegrities
- Globally rigid augmentation of minimally rigid graphs in \(\mathbb{R}^2\)
- Enumerating rigid sphere packings
- On affine rigidity
- Unique low rank completability of partially filled matrices
- Minimum cost globally rigid subgraphs
- Global completability with applications to self-consistent quantum tomography
- The 2-dimensional rigidity of certain families of graphs
- On the universal rigidity of generic bar frameworks
- Localization from incomplete noisy distance measurements
- Combinatorial genericity and minimal rigidity
- scientific article; zbMATH DE number 3920492 (Why is no real title available?)
- scientific article; zbMATH DE number 17636 (Why is no real title available?)
- Generically globally rigid zeolites in the plane
- Geometric conditions of rigidity in nongeneric settings
- Generic global rigidity in general dimension
- Global rigidity of two-dimensional framework
- The number of realizations of a Laman graph
- Noisy Euclidean Distance Realization: Robust Facial Reduction and the Pareto Frontier
- Necessary conditions for the generic global rigidity of frameworks on surfaces
- scientific article; zbMATH DE number 817406 (Why is no real title available?)
- Method of moments for 3D single particle \textit{ab initio} modeling with non-uniform distribution of viewing angles
- Global rigidity of 2D linearly constrained frameworks
- Epsilon local rigidity and numerical algebraic geometry
- Assigned and unassigned distance geometry: applications to biological molecules and nanostructures
- Globally rigid augmentation of rigid graphs
- Rigidity of random subgraphs and eigenvalues of stiffness matrices
- Frameworks with Coordinated Edge Motions
- Globally rigid graphs are fully reconstructible
- Global Rigidity of Unit Ball Graphs
- Generic unlabeled global rigidity
- Global registration of multiple point clouds using semidefinite programming
- Local, dimensional and universal rigidities: a unified Gram matrix approach
- Generic Global Rigidity in Complex and Pseudo-Euclidean Spaces
- Globally linked pairs of vertices in rigid frameworks
- 1-extensions and global rigidity of generic direction-length frameworks
- Bounded direction-length frameworks
- Necessary conditions for the global rigidity of direction-length frameworks
- Spectral radius conditions for the rigidity of graphs
- A necessary condition for generic rigidity of bar‐and‐joint frameworks in d‐space
- Classifying the globally rigid edge‐transitive graphs and distance‐regular graphs in the plane
- Coincident-point rigidity in normed planes
- Cycle-based formulations in distance geometry
- Graph rigidity properties of Ramanujan graphs
- Sharp threshold for rigidity of random graphs
- Nonlinear algebra and applications
- Global Rigidity of Line Constrained Frameworks
- New classes of counterexamples to Hendrickson's global rigidity conjecture
- Partial reflections and globally linked pairs in rigid graphs
- Computing maximum likelihood thresholds using graph rigidity
- Maximum likelihood thresholds via graph rigidity
- Uniquely realisable graphs in analytic normed planes
- Reconstructing a point set from a random subset of its pairwise distances
- Global rigidity of triangulated manifolds
- Rigid frameworks with dilation constraints
- Reconstructing almost all of a point set in \(\mathbb{R}^d\) from randomly revealed pairwise distances
- Equilibrium stresses in frameworks via symmetric averaging
- Generic global rigidity in _p-space and the identifiability of the p-Cayley-Menger varieties
- MFO-RIMS tandem workshop: Optimization, theoretical computer science and algebraic geometry: convexity and beyond. Abstracts from the MFO-RIMS tandem workshop held February 16--21, 2025
- On the uniqueness of collections of pennies and marbles
- Minimal counterexamples to Hendrickson's conjecture on globally rigid graphs
- Stability of sequential lateration and of stress minimization in the presence of noise
- Globally linked pairs and cheapest globally rigid supergraphs
- Generic global rigidity of body-bar frameworks
- Every \(d(d + 1)\)-connected graph is globally rigid in \(\mathbb{R}^d\)
This page was built for publication: Characterizing generic global rigidity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3584599)
