New classes of counterexamples to Hendrickson's global rigidity conjecture

DOI10.1007/S00454-010-9259-YMaRDI QIDQ633205zbMATH OpenOpenAlexWikidataFDO

Authors Samuel Frank, Jiayang Jiang

Publication date 31 March 2011

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

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

Mathematics Subject Classification ID

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

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.

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

Cites work

• scientific article; zbMATH DE number 17636 (Why is no real title available?)
• Characterizing generic global rigidity
• Conditions for Unique Graph Realizations
• Connected rigidity matroids and unique realizations of graphs
• Generic global rigidity
• Global rigidity: The effect of coning
• The Rigidity of Graphs
• When is a bipartite graph a rigid framework?

Cited in

(7)

• Characterizing generic global rigidity
• scientific article; zbMATH DE number 17636 (Why is no real title available?)
• Combining globally rigid frameworks
• Refuting Ehrenfeucht conjecture on rigid models
• Generic global rigidity of body-hinge frameworks
• Globally linked pairs of vertices in rigid frameworks
• 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)