TR-2008-08

Operations Preserving Global Rigidity of Generic Direction-Length Frameworks

Bill Jackson, Tibor Jordán

Published in:
Journal on Computational Geometry and Applications, Volume 20, Number 6, December 2010, pp. 685-706.

A two-dimensional mixed framework is a pair (G,p), where G=(V;D,L) is a graph whose edges are labeled as `direction' or `length' edges, and a map p from V to R². The label of an edge uv represents a direction or length constraint between p(u) and p(v). The framework (G,p) is called globally rigid if every other framework (G,q) in which the direction or length between the endvertices of corresponding edges is the same is `congruent' to (G,p), i.e. it can be obtained from (G,p) by a translation and possibly by a dilation by -1.
 
We show that labeled versions of the two Henneberg operations (0-extension and 1-extension) preserve global rigidity of generic mixed frameworks. These results, together with appropriate inductive constructions, can be used to verify generic global rigidity of special families of mixed graphs.

Bibtex entry:

@techreport{egres-08-08,

AUTHOR	=	{Jackson, Bill and Jord{\'a}n, Tibor},
TITLE	=	{Operations Preserving Global Rigidity of Generic Direction-Length Frameworks},
NOTE	=	{{\tt egres.elte.hu}},
INSTITUTION	=	{Egerv{\'a}ry Research Group, Budapest},
YEAR	=	{2008},
NUMBER	=	{TR-2008-08}

}