TR-2004-02

Rigid two-dimensional frameworks with three collinear points

Bill Jackson, Tibor Jordán

Published in:
Graphs and Combinatorics, December 2005, Volume 21, Issue 4, pp 427-444

Let G=(V,E) be a graph and x,y,z \in V be three designated vertices. We give a necessary and sufficient condition for the existence of a rigid two-dimensional framework (G,p), in which x,y,z are collinear. This result extends a classical result of Laman on the existence of a rigid framework on G. Our proof leads to an efficient algorithm which can test whether G satisfies the condition.

Bibtex entry:

@techreport{egres-04-02,

AUTHOR	=	{Jackson, Bill and Jord{\'a}n, Tibor},
TITLE	=	{Rigid two-dimensional frameworks with three collinear points},
NOTE	=	{{\tt egres.elte.hu}},
INSTITUTION	=	{Egerv{\'a}ry Research Group, Budapest},
YEAR	=	{2004},
NUMBER	=	{TR-2004-02}

}