Generic global rigidity of body-hinge frameworks

A d-dimensional body-hinge framework is a structure consisting of rigid bodies in d-space in which some pairs of bodies are connected by a hinge, restricting the relative position of the corresponding bodies. The framework is said to be globally rigid if every other arrangement of the bodies and their hinges can be obtained by a congruence of the space. The combinatorial structure of a body-hinge framework can be encoded by a multigraph H, in which the vertices correspond to the bodies and the edges correspond to the hinges. We prove that a generic body-hinge realization of a multigraph H   is globally rigid in RdRd, d≥3d≥3, if and only if ((d+12)−1)H−e contains (d+12) edge-disjoint spanning trees for all edges e   of ((d+12)−1)H. (For a multigraph H and integer k we use kH to denote the multigraph obtained from H by replacing each edge e of H by k parallel copies of e.) This implies an affirmative answer to a conjecture of Connelly, Whiteley, and the first author.We also consider bar-joint frameworks and show, for each d≥3d≥3, an infinite family of graphs satisfying Hendrickson's well-known necessary conditions for generic global rigidity in RdRd (that is, (d+1)(d+1)-connectivity and redundant rigidity) which are not generically globally rigid in RdRd. The existence of these families disproves a number of conjectures, due to Connelly, Connelly and Whiteley, and the third author, respectively.