Published in:
J. Combinatorial Theory, Ser. B., Vol. 103, Issue 6, November 2013, pp. 689-705.
A basic geometric question is to determine when a given framework G(p)
is globally rigid in Euclidean space R^{d}, where G is a finite graph and p is a
configuration of points corresponding to the vertices of G. G(p) is globally rigid
in R^{d} if for any other configuration q for G such that the edge lengths of G(q)
are the same as the corresponding edge lengths of G(p), then p is congruent to
q. A framework G(p) is redundantly rigid, if it is rigid and it remains rigid after
the removal of any edge of G. Hendrickson [9] proved that redundant rigidity
is a necessary condition for generic global rigidity, as is (d + 1)-connectivity.
Recent results in [2] and [10] have shown that when the configuration p is
generic and d=2, redundant rigidity and 3-connectivity are also sufficient - a
good combinatorial characterization that only depends on G and can be checked
in polynomial time. It appears that a similar result for d=3 is beyond the
scope of present techniques and there are counterexamples to the sufficiency of
Hendrickson's conditions.
However, there is a special class of generic frameworks that have polynomial
time algorithms for their generic rigidity (and redundant rigidity) in R^{d}
for any d, as shown in [19], namely generic body-and-bar frameworks. Such
frameworks are constructed from a finite number of rigid bodies that are connected
by bars generically placed with respect to each body. We show that a
body-and-bar framework is generically globally rigid in R^{d}, for any d, if it
is redundantly rigid. As a consequence there is a deterministic polynomial time
combinatorial algorithm on the graph to determine the generic global rigidity
of body-and-bar frameworks in any dimension.
Bibtex entry:
@techreport{egres-09-13,
AUTHOR | = | {Connelly, Robert and Jord{\'a}n, Tibor and Whiteley, Walter}, |
TITLE | = | {Generic global rigidity of body-bar frameworks}, |
NOTE | = | {{\tt www.cs.elte.hu/egres}}, |
INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
YEAR | = | {2009}, |
NUMBER | = | {TR-2009-13} |