|
Published in:
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:
| AUTHOR | = | {Jord{\'a}n, Tibor and Kir{\'a}ly, Csaba and Tanigawa, Shin-ichi}, |
| TITLE | = | {Generic global rigidity of body-hinge frameworks}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2014}, |
| NUMBER | = | {TR-2014-06} |