Sufficient conditions for the global rigidity of graphs

DOI10.1016/J.JCTB.2015.01.003zbMATH Open1315.05039arXiv1403.3742OpenAlexW2124036733MaRDI QIDQ2347845FDOQ2347845

Authors: Shin-Ichi Tanigawa 

Publication date: 10 June 2015

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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 $vinV$.

Full work available at URL: https://arxiv.org/abs/1403.3742

Recommendations

• Minimally globally rigid graphs
• Characterizing generic global rigidity
• Sufficient conditions for 2-dimensional global rigidity
• Global rigidity of periodic graphs under fixed-lattice representations
• Sufficient conditions for the global rigidity of periodic graphs

zbMATH Keywords

rigidity of graphsglobal rigidityrigidity matroidunique graph realizations

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Combinatorial aspects of matroids and geometric lattices (05B35)

Cites Work

• Connected rigidity matroids and unique realizations of graphs
• Generic global rigidity
• On graphs and rigidity of plane skeletal structures
• Characterizing generic global rigidity
• Conditions for Unique Graph Realizations
• Title not available (Why is that?)
• A proof of the molecular conjecture
• The Union of Matroids and the Rigidity of Frameworks
• The Rigidity of Graphs
• Rigidity of multi-graphs. I: Linking rigid bodies in n-space
• Constructive characterizations for packing and covering with trees
• Linking (n-2)-dimensional panels in n-space. II: (n-2,2)-frameworks and body and Hinge structures
• Globally linked pairs of vertices in equivalent realizations of graphs
• Title not available (Why is that?)
• Global rigidity: The effect of coning
• Rigidity and energy
• A proof of Connelly's conjecture on 3-connected circuits of the rigidity matroid.
• Generic rigidity matroids with Dilworth truncations
• Linking \((n-2)\)-dimensional panels in \(n\)-space. I: \((k-1,k)\)-graphs and \((k-1,k)\)-frames
• When is a bipartite graph a rigid framework?
• Birigidity in the Plane
• New classes of counterexamples to Hendrickson's global rigidity conjecture
• Combinatorial rigidity. Graphs and matroids in the theory of rigid frameworks
• Generic Global Rigidity in Complex and Pseudo-Euclidean Spaces
• Combining globally rigid frameworks
• Independence and port oracles for matroids, with an application to computational learning theory

Cited In (33)

• Operations preserving the global rigidity of graphs and frameworks in the plane
• Rigidity of random subgraphs and eigenvalues of stiffness matrices
• Ear‐decompositions, minimally connected matroids and rigid graphs
• Computing maximum likelihood thresholds using graph rigidity
• A sufficient connectivity condition for generic rigidity in the plane
• Globally rigid circuits of the direction-length rigidity matroid
• A note on generic rigidity of graphs in higher dimension
• Equivalence of continuous, local and infinitesimal rigidity in normed spaces
• Globally rigid powers of graphs
• Characterizing redundant rigidity and redundant global rigidity of body-hinge graphs
• Sufficient conditions for 2-dimensional global rigidity
• Enumerating grid layouts of graphs
• Unique low rank completability of partially filled matrices
• Classifying the globally rigid edge‐transitive graphs and distance‐regular graphs in the plane
• Minimum size highly redundantly rigid graphs in the plane
• Generic global rigidity of body-hinge frameworks
• Generic global rigidity
• Global rigidity of triangulated manifolds
• On the Existence of Paradoxical Motions of Generically Rigid Graphs on the Sphere
• Sharp threshold for rigidity of random graphs
• Redundantly globally rigid braced triangulations
• Minimally globally rigid graphs
• Sufficient conditions for the global rigidity of periodic graphs
• Characterizing generic global rigidity
• Global rigidity of periodic graphs under fixed-lattice representations
• On the global rigidity of tensegrity graphs
• On minimally highly vertex-redundantly rigid graphs
• Extremal families of redundantly rigid graphs in three dimensions
• Global Rigidity of Unit Ball Graphs
• Universal rigidity of complete bipartite graphs
• Global rigidity of triangulations with braces
• Globally rigid augmentation of rigid graphs
• Vertex splitting, coincident realisations, and global rigidity of braced triangulations

This page was built for publication: Sufficient conditions for the global rigidity of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2347845)