TR-2012-08

Rigid two-dimensional frameworks with two coincident points

Zsolt Fekete, Tibor Jordán, Viktória Kaszanitzky

Published in:
Graphs and Combinatorics, January 2014.

Let $G=(V,E)$ be a graph and $u,v\in V$ be two distinct vertices. We give a necessary and sufficient condition for the existence of an infinitesimally rigid two-dimensional bar-and-joint framework $(G,p)$, in which the positions of $u$ and $v$ coincide. We also determine the rank function of the corresponding modified generic rigidity matroid on ground-set $E$. The results lead to efficient algorithms for testing whether a graph has such a coincident realization with respect to a designated vertex pair and, more generally, for computing the rank of $G$ in the matroid.

Bibtex entry:

@techreport{egres-12-08,

AUTHOR	=	{Fekete, Zsolt and Jord{\'a}n, Tibor and Kaszanitzky, Vikt{\'o}ria},
TITLE	=	{Rigid two-dimensional frameworks with two coincident points},
NOTE	=	{{\tt egres.elte.hu}},
INSTITUTION	=	{Egerv{\'a}ry Research Group, Budapest},
YEAR	=	{2012},
NUMBER	=	{TR-2012-08}

}