TR-2002-12

Connected rigidity matroids and unique realizations of graphs

Bill Jackson, Tibor Jordán

Published in:
J. Combin. Theory Ser. B 94 (2005) 1-29.

A d-dimensional framework is a straight line embedding of a graph G in R^d. We shall only consider generic frameworks, in which the co-ordinates of all the vertices of G are algebraically independent. Two frameworks for G are equivalent if corresponding edges in the two frameworks have the same length. A framework is a unique realization of G in R^d if every equivalent framework can be obtained from it by a rigid congruence of R^d. Bruce Hendrickson proved that if G has a unique realization in R^d then G is (d+1)-connected and redundantly rigid. He conjectured that every realization of a (d+1)-connected and redundantly rigid graph in R^d is unique. This conjecture is true for d=1 but was disproved by Robert Connelly for d \geq 3. We resolve the remaining open case by showing that Hendrickson's conjecture is true for d=2. As a corollary we deduce that every realization of a 6-connected graph as a 2-dimensional generic framework is a unique realization. Our proof is based on a new inductive characterization of 3-connected graphs whose rigidity matroid is connected.

Bibtex entry:

@techreport{egres-02-12,

AUTHOR	=	{Jackson, Bill and Jord{\'a}n, Tibor},
TITLE	=	{Connected rigidity matroids and unique realizations of graphs},
NOTE	=	{{\tt egres.elte.hu}},
INSTITUTION	=	{Egerv{\'a}ry Research Group, Budapest},
YEAR	=	{2002},
NUMBER	=	{TR-2002-12}

}