TR-2004-11

Rigid realizations of graphs on small grids

Zsolt Fekete, Tibor Jordán

Published in:
Computational Geometry, Vol. 32, Issue 3 216-222, 2005.

A framework (G,p) is a graph G=(V,E) and a mapping p: V \to R². We prove that if (G,p) is an infinitesimally rigid framework then there is an infinitesimally rigid framework (G,q) for which the points q(v), v \in V(G), are distinct points of the k * k grid, where k=\lceil {\sqrt{|V|-1}}\rceil+9. We also show that such a framework on G can be constructed in O(|V|³) time.

Bibtex entry:

@techreport{egres-04-11,

AUTHOR	=	{Fekete, Zsolt and Jord{\'a}n, Tibor},
TITLE	=	{Rigid realizations of graphs on small grids},
NOTE	=	{{\tt egres.elte.hu}},
INSTITUTION	=	{Egerv{\'a}ry Research Group, Budapest},
YEAR	=	{2004},
NUMBER	=	{TR-2004-11}

}