Characterizing generic global rigidity
From MaRDI portal
Publication:3584599
DOI10.1353/AJM.0.0132zbMATH Open1202.52020arXiv0710.0926OpenAlexW2107850743MaRDI QIDQ3584599FDOQ3584599
Authors: Steven J. Gortler, Alexander D. Healy, Dylan P. Thurston 
Publication date: 30 August 2010
Published in: American Journal of Mathematics (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/0710.0926
Recommendations
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)
Cited In (97)
- The number of realizations of a Laman graph
- Globally linked pairs of vertices in equivalent realizations of graphs
- Title not available (Why is that?)
- Recent results on assigned and unassigned distance geometry with applications to protein molecules and nanostructures
- The unassigned distance geometry problem
- 1-extensions and global rigidity of generic direction-length frameworks
- Characterizing the universal rigidity of generic frameworks
- Generically globally rigid zeolites in the plane
- A proof of Connelly's conjecture on 3-connected circuits of the rigidity matroid.
- Bounded direction-length frameworks
- Necessary conditions for the global rigidity of direction-length frameworks
- A necessary condition for generic rigidity of bar‐and‐joint frameworks in d‐space
- Title not available (Why is that?)
- On the universal rigidity of generic bar frameworks
- Local, dimensional and universal rigidities: a unified Gram matrix approach
- On affine rigidity
- On dimensional rigidity of bar-and-joint frameworks
- Globally rigid circuits of the direction-length rigidity matroid
- The rigidity of infinite graphs
- A note on generic rigidity of graphs in higher dimension
- Equivalent realisations of a rigid graph
- Global rigidity of generic frameworks on the cylinder
- Generic Global Rigidity in Complex and Pseudo-Euclidean Spaces
- On stress matrices of \((d + 1)\)-lateration frameworks in general position
- Algorithms for detecting dependencies and rigid subsystems for CAD
- Necessary conditions for the generic global rigidity of frameworks on surfaces
- Iterative universal rigidity
- 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
- Generic unlabeled global rigidity
- Combining globally rigid frameworks
- Graph reconstruction from unlabeled edge lengths
- Global rigidity of 2D linearly constrained frameworks
- Unique low rank completability of partially filled matrices
- Global completability with applications to self-consistent quantum tomography
- 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\)
- Combinatorial genericity and minimal rigidity
- Generically globally rigid graphs have generic universally rigid frameworks
- Generic global rigidity of body-hinge frameworks
- Generic global rigidity
- Global rigidity: The effect of coning
- New classes of counterexamples to Hendrickson's global rigidity conjecture
- Generalised rigid body motions in non-Euclidean planes with applications to global rigidity
- Noisy Euclidean Distance Realization: Robust Facial Reduction and the Pareto Frontier
- Minimally globally rigid graphs
- Globally linked pairs of vertices in rigid frameworks
- Geometric conditions of rigidity in nongeneric settings
- Localization from incomplete noisy distance measurements
- Generic global rigidity in general dimension
- Title not available (Why is that?)
- Assigned and unassigned distance geometry: applications to biological molecules and nanostructures
- On the global rigidity of tensegrity graphs
- The 2-dimensional rigidity of certain families of graphs
- Sufficient conditions for the global rigidity of graphs
- Globally rigid augmentation of rigid graphs
- On bar frameworks, stress matrices and semidefinite programming
- Global registration of multiple point clouds using semidefinite programming
- Spectral conditions for graph rigidity in the Euclidean plane
- Graph rigidity properties of Ramanujan graphs
- Rigidity of random subgraphs and eigenvalues of stiffness matrices
- Enumerating rigid sphere packings
- Minimum cost globally rigid subgraphs
- Computing maximum likelihood thresholds using graph rigidity
- Partial reflections and globally linked pairs in rigid graphs
- Global rigidity of two-dimensional framework
- Maximum likelihood thresholds via graph rigidity
- Globally rigid powers of graphs
- Spectral radius conditions for the rigidity of graphs
- Globally rigid graphs are fully reconstructible
- Method of moments for 3D single particle \textit{ab initio} modeling with non-uniform distribution of viewing angles
- An extension of the angular synchronization problem to the heterogeneous setting
- Nonlinear algebra and applications
- Classifying the globally rigid edge‐transitive graphs and distance‐regular graphs in the plane
- Fully distributed affine formation control of general linear systems with uncertainty
- Uniquely realisable graphs in analytic normed planes
- Reconstructing a point set from a random subset of its pairwise distances
- 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
- Rigid frameworks with dilation constraints
- Sharp threshold for rigidity of random graphs
- Frameworks with Coordinated Edge Motions
- Bearing-only distributed localization: a unified barycentric approach
- Sufficient conditions for the global rigidity of periodic graphs
- Global rigidity of periodic graphs under fixed-lattice representations
- Cycle-based formulations in distance geometry
- Globally rigid augmentation of minimally rigid graphs in \(\mathbb{R}^2\)
- \(K_{5, 5}\) is fully reconstructible in \(\mathbb{C}^3\)
- Global Rigidity of Unit Ball Graphs
- Global rigidity of triangulations with braces
- Vertex splitting, coincident realisations, and global rigidity of braced triangulations
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)
