TR-2008-01

A sufficient connectivity condition for generic rigidity in the plane

Bill Jackson, Tibor Jordán

Published in:
Discrete Applied Mathematics, 157 (2009) 1965-1968.

A graph G=(V,E) is said to be 6-mixed-connected if G-U-D is connected for all sets U \subseteq V and D \subseteq E which satisfy 2|U|+|D|\leq 5. In this note we prove that 6-mixed-connected graphs are (redundantly globally) rigid in the plane. This improves on a previous result of Lovász and Yemini.

Bibtex entry:

@techreport{egres-08-01,

AUTHOR	=	{Jackson, Bill and Jord{\'a}n, Tibor},
TITLE	=	{A sufficient connectivity condition for generic rigidity in the plane},
NOTE	=	{{\tt egres.elte.hu}},
INSTITUTION	=	{Egerv{\'a}ry Research Group, Budapest},
YEAR	=	{2008},
NUMBER	=	{TR-2008-01}

}