Constructing Isostatic Frameworks for the $\ell^1$ and $\ell^\infty$ Plane

Abstract

We use a new coloured multi-graph constructive method to prove that if the edge-set of a graph $G=(V,E)$ has a partition into two spanning trees $T_1$ and $T_2$ then there is a map $p:V\to \mathbb{R}^2$, $p(v)=(p_1(v),p_2(v))$, such that $|p_i(u)-p_i(v)| \geqslant |p_{3-i}(u)-p_{3-i}(v)|$ for every edge $uv$ in $T_i$ ($i=1,2$). As a consequence, we solve an open problem on the realisability of minimally rigid bar-joint frameworks in the $\ell^1$ or $\ell^\infty$-plane. We also show how to adapt this technique to incorporate symmetry and indicate several related open problems on rigidity, redundant rigidity and forced symmetric rigidity in normed spaces.