TR-2014-06

Generic global rigidity of body-hinge frameworks

Tibor Jordán, Csaba Király, Shin-ichi Tanigawa



Abstract

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 $\R^d$, $d\geq 3$, if and only if $({d+1\choose 2}-1)H-e$ contains ${d+1\choose 2}$ edge-disjoint spanning trees for all edges $e$ of $({d+1\choose 2}-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\geq 3$, an infinite family of graphs satisfying Hendrickson's well-known necessary conditions for generic global rigidity in $\R^d$ (that is, $(d+1)$-connectivity and redundant rigidity) which are not generically globally rigid in $\R^d$. The existence of these families disproves a number of conjectures, due to Connelly, Connelly and Whiteley, and the third author, respectively.


Bibtex entry:

@techreport{egres-14-06,
AUTHOR = {Jord{\'a}n, Tibor and Kir{\'a}ly, Csaba and Tanigawa, Shin-ichi},
TITLE = {Generic global rigidity of body-hinge frameworks},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2014},
NUMBER = {TR-2014-06}
}


Last modification: 26.9.2017. Please email your comments to Tamás Király!