The d-dimensional rigidity matroid of sparse graphs

Bill Jackson, Tibor Jordán

Published in:
Journal of Combinatorial Theory B 95 1 (2005) 118-133

Abstract

Let ${\cal R}_d(G)$ be the $d$-dimensional rigidity matroid for a graph $G=(V,E)$. For $X\subseteq V$ let $i(X)$ be the number of edges in the subgraph of $G$ induced by $X$. We derive a min-max formula which determines the rank function in ${\cal R}_d(G)$ when $G$ has maximum degree at most $d+2$ and minimum degree at most $d+1$. We also show that if $d$ is even and $i(X)\leq \frac{1}{2}[(d+2)|X| -(2d+2)]$ for all $X\subseteq V$ with $|X|\geq 2$ then $E$ is independent in ${\cal R}_d(G)$. We conjecture that the latter result holds for all $d\geq 2$ and prove this for the special case when $d=3$. We use the independence result for even $d$ to show that if the connectivity of $G$ is sufficiently large in comparison to $d$ then $E$ has large rank in ${\cal R}_{d}(G)$. We use the case $d=4$ to show that, if $G$ is $10$-connected, then $G$ can be made rigid in ${\mathbb{R}}^{3}$ by pinning down approximately three quarters of its vertices.

Bibtex entry:

@techreport{egres-03-06,
AUTHOR = {Jackson, Bill and Jord{\'a}n, Tibor},
TITLE = {The $d$-dimensional rigidity matroid of sparse graphs},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2003},
NUMBER = {TR-2003-06}
}