TR-2006-16

Operations preserving the global rigidity of graphs and frameworks in the plane

Tibor Jordán, Zoltán Szabadka

Published in:
Computational Geometry, 42 (2009) 511-521.

A straight-line realization of (or a bar-and-joint framework on) graph G in R^d is said to be globally rigid if it is congruent to every other realization of G with the same edge lengths. A graph G is called globally rigid in R^d if every generic realization of G is globally rigid. We give an algorithm for constructing a globally rigid realization of globally rigid graphs in R². If G is triangle-reducible, which is a subfamily of globally rigid graphs that includes Cauchy graphs as well as Grünbaum graphs, the constructed realization will also be infinitesimally rigid.
 
Our algorithm is based on an inductive construction of globally rigid graphs which uses Henneberg 1-extensions and edge additions. We show that vertex splitting, which is another well-known operation in combinatorial rigidity, also preserves global rigidity in R².

Bibtex entry:

@techreport{egres-06-16,

AUTHOR	=	{Jord{\'a}n, Tibor and Szabadka, Zolt{\'a}n},
TITLE	=	{Operations preserving the global rigidity of graphs and frameworks in the plane},
NOTE	=	{{\tt egres.elte.hu}},
INSTITUTION	=	{Egerv{\'a}ry Research Group, Budapest},
YEAR	=	{2006},
NUMBER	=	{TR-2006-16}

}