Characterizing generic global rigidity
From MaRDI portal
Publication:3584599
randomized algorithmdeterministic algorithmGauss mapgeneric frameworkequilibrium stress matrixgeneric local rigidity
Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62) Rods (beams, columns, shafts, arches, rings, etc.) (74K10) Distance geometry (51K99) Rigidity and flexibility of structures (aspects of discrete geometry) (52C25) Relations of low-dimensional topology with graph theory (57M15) Embeddings and immersions in PL-topology (57Q35) Differential geometric aspects in kinematics (53A17) Statics (70C99)
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
(97)- Globally rigid augmentation of rigid graphs
- Geometric conditions of rigidity in nongeneric settings
- Algorithms for detecting dependencies and rigid subsystems for CAD
- 1-extensions and global rigidity of generic direction-length frameworks
- Global rigidity of generic frameworks on the cylinder
- On bar frameworks, stress matrices and semidefinite programming
- Noisy Euclidean Distance Realization: Robust Facial Reduction and the Pareto Frontier
- On stress matrices of \((d + 1)\)-lateration frameworks in general position
- The 2-dimensional rigidity of certain families of graphs
- Global registration of multiple point clouds using semidefinite programming
- On the global rigidity of tensegrity graphs
- Minimally globally rigid graphs
- scientific article; zbMATH DE number 817406 (Why is no real title available?)
- Graph reconstruction from unlabeled edge lengths
- Globally linked pairs of vertices in equivalent realizations of graphs
- The number of realizations of a Laman graph
- Generic unlabeled global rigidity
- Globally rigid circuits of the direction-length rigidity matroid
- Generically globally rigid graphs have generic universally rigid frameworks
- Generically globally rigid zeolites in the plane
- Stress matrices and global rigidity of frameworks on surfaces
- scientific article; zbMATH DE number 17636 (Why is no real title available?)
- Necessary conditions for the generic global rigidity of frameworks on surfaces
- A proof of Connelly's conjecture on 3-connected circuits of the rigidity matroid.
- Global rigidity: The effect of coning
- Recent results on assigned and unassigned distance geometry with applications to protein molecules and nanostructures
- Bounded direction-length frameworks
- Necessary conditions for the global rigidity of direction-length frameworks
- Combining globally rigid frameworks
- Localization from incomplete noisy distance measurements
- The rigidity of infinite graphs
- Local, dimensional and universal rigidities: a unified Gram matrix approach
- scientific article; zbMATH DE number 3920492 (Why is no real title available?)
- Global rigidity of 2D linearly constrained frameworks
- Global rigidity of 2-dimensional direction-length frameworks with connected rigidity matroids
- Generalised rigid body motions in non-Euclidean planes with applications to global rigidity
- On affine rigidity
- Characterizing the universal rigidity of generic frameworks
- Iterative universal rigidity
- A sufficient connectivity condition for rigidity and global rigidity of linearly constrained frameworks in \(\mathbb{R}^2\)
- On the maximal number of real embeddings of minimally rigid graphs in \(\mathbb{R}^2,\mathbb{R}^3\) and \(S^2\)
- Generic global rigidity of body-hinge frameworks
- Spectral conditions for graph rigidity in the Euclidean plane
- Generic Global Rigidity in Complex and Pseudo-Euclidean Spaces
- Globally linked pairs of vertices in rigid frameworks
- Generic global rigidity
- A note on generic rigidity of graphs in higher dimension
- A necessary condition for generic rigidity of bar‐and‐joint frameworks in d‐space
- Unique low rank completability of partially filled matrices
- On the universal rigidity of generic bar frameworks
- Finite and infinitesimal rigidity with polyhedral norms
- Global completability with applications to self-consistent quantum tomography
- Generic global rigidity in general dimension
- Assigned and unassigned distance geometry: applications to biological molecules and nanostructures
- Combinatorial genericity and minimal rigidity
- Characterizing the universal rigidity of generic tensegrities
- Equivalent realisations of a rigid graph
- Characterizing graphs with convex and connected Cayley configuration spaces
- The unassigned distance geometry problem
- New classes of counterexamples to Hendrickson's global rigidity conjecture
- Sufficient conditions for the global rigidity of graphs
- On dimensional rigidity of bar-and-joint frameworks
- Global rigidity of (quasi-)injective frameworks on the line
- Maximum likelihood thresholds via graph rigidity
- Rigidity of random subgraphs and eigenvalues of stiffness matrices
- Globally rigid graphs are fully reconstructible
- Enumerating rigid sphere packings
- Global rigidity of periodic graphs under fixed-lattice representations
- Frameworks with Coordinated Edge Motions
- Vertex splitting, coincident realisations, and global rigidity of braced triangulations
- Method of moments for 3D single particle \textit{ab initio} modeling with non-uniform distribution of viewing angles
- Global Rigidity of Line Constrained Frameworks
- Global rigidity of triangulations with braces
- \(K_{5, 5}\) is fully reconstructible in \(\mathbb{C}^3\)
- Nonlinear algebra and applications
- Rigid frameworks with dilation constraints
- Epsilon local rigidity and numerical algebraic geometry
- Minimum cost globally rigid subgraphs
- Cycle-based formulations in distance geometry
- Uniquely realisable graphs in analytic normed planes
- Globally rigid powers of graphs
- Graph rigidity properties of Ramanujan graphs
- Coincident-point rigidity in normed planes
- Reconstructing a point set from a random subset of its pairwise distances
- Bearing-only distributed localization: a unified barycentric approach
- Sufficient conditions for the global rigidity of periodic graphs
- Global Rigidity of Unit Ball Graphs
- Sharp threshold for rigidity of random graphs
- Computing maximum likelihood thresholds using graph rigidity
- Global rigidity of two-dimensional framework
- Partial reflections and globally linked pairs in rigid graphs
- Global rigidity of triangulated manifolds
- An extension of the angular synchronization problem to the heterogeneous setting
- Globally rigid augmentation of minimally rigid graphs in \(\mathbb{R}^2\)
- Spectral radius conditions for the rigidity of graphs
- Fully distributed affine formation control of general linear systems with uncertainty
- Classifying the globally rigid edge‐transitive graphs and distance‐regular graphs in the plane
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)
