TR-2005-09

On the rank function of the 3-dimensional rigidity matroid

Bill Jackson, Tibor Jordán

Published in:
International Journal on Computational Geometry and Applications, Vol. 16, Nos. 5-6 (2006) 415-429.

It is an open problem to find a good characterization for independence or, more generally, the rank function in the d-dimensional rigidity matroid of a graph when d \geq 3. In this paper we give a brief survey of existing lower and upper bounds on the rank of the 3-dimensional rigidity matroid of a graph and introduce a new upper bound, which may lead to the desired good characterization.

Bibtex entry:

@techreport{egres-05-09,

AUTHOR	=	{Jackson, Bill and Jord{\'a}n, Tibor},
TITLE	=	{On the rank function of the 3-dimensional rigidity matroid},
NOTE	=	{{\tt egres.elte.hu}},
INSTITUTION	=	{Egerv{\'a}ry Research Group, Budapest},
YEAR	=	{2005},
NUMBER	=	{TR-2005-09}

}