New classes of counterexamples to Hendrickson's global rigidity conjecture

DOI10.1007/S00454-010-9259-YzbMATH Open1220.05024arXiv0909.2893OpenAlexW1993173879WikidataQ123142850 ScholiaQ123142850MaRDI QIDQ633205FDOQ633205

Authors: Samuel Frank, Jiayang Jiang 

Publication date: 31 March 2011

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Abstract: We examine the generic local and global rigidity of various graphs in R^d. Bruce Hendrickson showed that some necessary conditions for generic global rigidity are (d+1)-connectedness and generic redundant rigidity and hypothesized that they were sufficient in all dimensions. We analyze two classes of graphs that satisfy Hendrickson's conditions for generic global rigidity, yet fail to be generically globally rigid. We find a large family of bipartite graphs for d > 3, and we define a construction that generates infinitely many graphs in R^5. Finally, we state some conjectures for further exploration.

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

Recommendations

• scientific article; zbMATH DE number 17636
• Minimally globally rigid graphs
• Generic global rigidity of body-hinge frameworks
• Characterizing generic global rigidity
• Globally rigid powers of graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Rigidity and flexibility of structures (aspects of discrete geometry) (52C25)

Cites Work

• Connected rigidity matroids and unique realizations of graphs
• Generic global rigidity
• Characterizing generic global rigidity
• Title not available (Why is that?)
• Conditions for Unique Graph Realizations
• The Rigidity of Graphs
• Global rigidity: The effect of coning
• When is a bipartite graph a rigid framework?

Cited In (7)

• Title not available (Why is that?)
• Combining globally rigid frameworks
• Generic global rigidity of body-hinge frameworks
• Globally linked pairs of vertices in rigid frameworks
• Refuting Ehrenfeucht conjecture on rigid models
• Characterizing generic global rigidity
• Sufficient conditions for the global rigidity of graphs

This page was built for publication: New classes of counterexamples to Hendrickson's global rigidity conjecture

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