Rigid graphs in cylindrical normed spaces

Abstract

We characterise rigid graphs for cylindrical normed spaces $Z=X{\oplus }_{\infty }\mathbb{R}$ where $X$ is a finite dimensional real normed linear space and $Z$ is endowed with the product norm. In particular, we obtain purely combinatorial characterisations of minimal rigidity for a large class of 3-dimensional cylindrical normed spaces; for example, when $X$ is an ${\ell }_p$-plane with $p\in (1,\infty )$. We combine these results with recent work of Cros et al. to characterise rigid graphs in the 4-dimensional cylindrical space $({\mathbb{R}}^2{\oplus }_1\mathbb{R}){\oplus }_{\infty }\mathbb{R}$. These are among the first combinatorial characterisations of rigid graphs in normed spaces of dimension greater than 2. Examples of rigid graphs are presented and algorithmic aspects are discussed.

28 pages