\(\ell^1\) and \(\ell^\infty\) plane

Katie Clinch ; Derek Kitson¹

¹Lancaster University

The electronic journal of combinatorics, Tome 27 (2020) no. 2

Résumé

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.

Détail

DOI : 10.37236/8196

Classification : 05C15, 05C75, 52A21, 52C25
Mots-clés : \(d\)-tree decomposition, graphs rigidity