|
A block and hole graph is obtained from the graph of a plane triangulation
by removing the interiors of some discs, defined by their boundary cycles,
and then rigidifying the vertex sets of some of these cycles by adding new
vertices and edges. These rigid parts form the so-called blocks, while the remaining
cycles define the holes.
Cruickshank, Kitson, and Power proved that a
a block and hole
graph $G$ with a single block is generically minimally rigid in $\R^3$
if and only if $G$ is $(3,6)$-sparse and has $3|V(G)|-6$ edges.
This result implies that there is an efficient algorithm for testing
whether such a graph is rigid, provided it has exactly $3|V(G)|-6$ edges.
In this paper we extend these results to block and hole graphs $G$ with a single block and
an arbitrary number of edges. The extension is based on a new formula for
the degrees of freedom of such a graph. It also enables us to find a
smallest set of new edges whose addition makes $G$ rigid.
We also point out that there is an underlying matroid which can be
defined by $(3,6)$-sparsity.
Bibtex entry:
| AUTHOR | = | {Jord{\'a}n, Tibor}, |
| TITLE | = | {Rigid block and hole graphs with a single block}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2021}, |
| NUMBER | = | {TR-2021-09} |