Abstract. We characterize rigid graphs for cylindrical normed spaces [Formula: see text] where [Formula: see text] is a finite-dimensional real normed linear space and [Formula: see text] is endowed with the product norm. In particular, we obtain purely combinatorial characterizations of minimal rigidity for a large class of 3-dimensional cylindrical normed spaces; for example, when [Formula: see text] is an [Formula: see text]-plane with [Formula: see text]. We also characterize rigid graphs in the 4-dimensional cylindrical space [Formula: see text]. These are among the first combinatorial characterizations of rigid graphs in normed spaces of dimension [Formula: see text].

Abstract We consider the problem of finding an inductive construction, based on vertex splitting, of triangulated spheres with a fixed number of additional edges (braces). We show that for any positive integer b there is such an inductive construction of triangulations with b braces, having finitely many base graphs. In particular we establish a bound for the maximum size of a base graph with b braces that is linear in b . In the case that $$b=1$$ b = 1 or 2 we determine the list of base graphs explicitly. Using these results we show that doubly braced triangulations are (generically) minimally rigid in two distinct geometric contexts arising from a hypercylinder in $$\mathbb {R}^4$$ R 4 and a class of mixed norms on $$\mathbb {R}^3$$ R 3 .

Abstract We present three results which support the conjecture that a graph is minimally rigid in d-dimensional $$\ell _p$$ ℓ p -space, where $$p\in (1,\infty )$$ p ∈ ( 1 , ∞ ) and $$p\not =2$$ p ≠ 2 , if and only if it is (d, d)-tight. Firstly, we introduce a graph bracing operation which preserves independence in the generic rigidity matroid when passing from $$\ell _p^d$$ ℓ p d to $$\ell _p^{d+1}$$ ℓ p d + 1 . We then prove that every (d, d)-sparse graph with minimum degree at most $$d+1$$ d + 1 and maximum degree at most $$d+2$$ d + 2 is independent in $$\ell _p^d$$ ℓ p d . Finally, we prove that every triangulation of the projective plane is minimally rigid in $$\ell _p^3$$ ℓ p 3 . A catalogue of rigidity preserving graph moves is also provided for the more general class of strictly convex and smooth normed spaces and we show that every triangulation of the sphere is independent for 3-dimensional spaces in this class.

A rigidity theory is developed for countably infinite simple graphs in $${\mathbb {R}}^d$$ . Generalisations are obtained for the Laman combinatorial characterisation of generic infinitesimal rigidity for finite graphs in $${\mathbb {R}}^2$$ and Tay’s multi-graph characterisation of generic infinitesimal rigidity for finite body-bar frameworks in $${\mathbb {R}}^d$$ . Analogous results are obtained for the classical non-Euclidean $$\ell ^q$$ norms.

Combinatorial characterisations are obtained of symmetric and anti-symmetric infinitesimal rigidity for two-dimensional frameworks with reflectional symmetry in the case of norms where the unit ball is a quadrilateral and where the reflection acts freely on the vertex set. At the framework level, these characterisations are given in terms of induced monochrome subgraph decompositions, and at the graph level they are given in terms of sparsity counts and recursive construction sequences for the corresponding signed quotient graphs.

We characterise finite and infinitesimal rigidity for bar-joint frameworks in $${\mathbb {R}}^d$$ with respect to polyhedral norms (i.e. norms with closed unit ball $${\mathcal {P}}$$ , a convex d-dimensional polytope). Infinitesimal and continuous rigidity are shown to be equivalent for finite frameworks in $${\mathbb {R}}^d$$ which are well-positioned with respect to $${\mathcal {P}}$$ . An edge-labelling determined by the facets of the unit ball and placement of the framework is used to characterise infinitesimal rigidity in $${\mathbb {R}}^d$$ in terms of monochrome spanning trees. An analogue of Laman’s theorem is obtained for all polyhedral norms on $${\mathbb {R}}^2$$ .