Rigid graphs and an augmentation problem

Csaba Király


A graph $G=(V,E)$ is called $(k,\ell)$-tight if $|E(X)|\leq k|X|-\ell$ for all $X\sbse V$ with $|X|\geq 2$ and $|E|=k|V|-\ell$. A graph $G$ is called $(k,\ell)$-redundant if $G-e$ has a spanning $(k,\ell)$-tight subgraph for all $e\in E$. We consider the following augmentation problem. Given a graph $G=(V,E)$ that has a $(k,\ell)$-tight spanning subgraph, find a graph $H=(V,F)$ with minimum number of edges, such that $G+H$ is $(k,\ell)$-redundant.
In this paper, we give a polynomial algorithm for this augmentation problem for $k\geq \ell$. We also give a polynomial algorithm for the case where $G$ is a $(k,\ell)$-tight graph with $k<\ell\leq \frac{3}{2}k$. As $(k,\ell)$-tight graphs play an important role in rigidity theory, these algorithms can be used to make several types of bar-and-joint frameworks redundantly rigid by adding a smallest set of new bars.

Bibtex entry:

AUTHOR = {Kir{\'a}ly, Csaba},
TITLE = {Rigid graphs and an augmentation problem},
NOTE= {{\tt}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2015},
NUMBER = {TR-2015-03}

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