Sufficient Conditions for the Global Rigidity of Graphs
Preprint
Abstract
We investigate how to find generic and globally rigid realizations of graphs in $\mathbb{R}^d$ based on elementary geometric observations. Our arguments lead to new proofs of a combinatorial characterization of the global rigidity of graphs in $\mathbb{R}^2$ by Jackson and Jord\'an and that of body-bar graphs in $\mathbb{R}^d$ recently shown by Connelly, Jord\'an, and Whiteley. We also extend the 1-extension theorem and Connelly's composition theorem, which are main tools for generating globally rigid graphs in $\mathbb{R}^d$. In particular we show that any vertex-redundantly rigid graph in $\mathbb{R}^d$ is globally rigid in $\mathbb{R}^d$, where a graph $G=(V,E)$ is called vertex-redundantly rigid if $G-v$ is rigid for any $v\in V$.
Keywords
All Related Versions
This publication has 23 references indexed in Scilit:
- Generic Global Rigidity in Complex and Pseudo-Euclidean Spaces2014
- Globally Linked Pairs of Vertices in Rigid Frameworks2014
- New Classes of Counterexamples to Hendrickson’s Global Rigidity ConjectureDiscrete & Computational Geometry, 2010
- Global Rigidity: The Effect of ConingDiscrete & Computational Geometry, 2009
- Globally Linked Pairs of Vertices in Equivalent Realizations of GraphsDiscrete & Computational Geometry, 2006
- Generic Global RigidityDiscrete & Computational Geometry, 2004
- Independence and port oracles for matroids, with an application to computational learning theoryCombinatorica, 1996
- Linking (n − 2)-dimensional panels inn-space II: (n − 2, 2)-frameworks and body and hinge structuresGraphs and Combinatorics, 1989
- Rigidity and energyInventiones Mathematicae, 1982
- On graphs and rigidity of plane skeletal structuresJournal of Engineering Mathematics, 1970