|
Published in:
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:
| AUTHOR | = | {Jackson, Bill and Jord{\'a}n, Tibor}, |
| TITLE | = | {The $d$-dimensional rigidity matroid of sparse graphs}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2003}, |
| NUMBER | = | {TR-2003-06} |