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