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.



Abstract

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 www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2012},
NUMBER = {TR-2012-08}
}


Last modification: 5.12.2018. Please email your comments to Tamás Király!