Block-and-hole graphs: Constructibility and $(3,0)$-sparsity

We show that minimally 3-rigid block-and-hole graphs, with one block or one hole, are characterised as those which are constructible from $K_3$ by vertex splitting, and also, as those having associated looped face graphs which are $(3,0)$-tight. This latter property can be verified in polynomial time by a form of pebble game algorithm. We also indicate connections to the rigidity properties of polyhedral surfaces known as origami and to graph rigidity in $\ell_p^3$ for $p\not=2$.

我们表明，具有一个块或一个洞的最小3 - 刚性块 - 洞图，其特征在于可通过顶点分裂从$K_3$构造而成，并且其相关的带环面图是(3, 0) - 紧的。后一种性质可以通过一种 pebble 博弈算法在多项式时间内得到验证。我们还指出了与被称为折纸的多面体表面的刚性性质以及在$p\neq2$时$\ell_p^3$中的图刚性的联系。