${\ell }_1$-Embeddability of Regular Quadrilateral Maps on the Torus and the Klein Bottle

Abstract

A connected graph is called ${\ell }_1$-embeddable if its shortest-path metric admits an isometric embedding into the ${\ell }_1$-space; equivalently, in the finite case, it admits a scale embedding into a hypercube. This paper gives a complete parameter-level classification of ${\ell }_1$-embeddability for regular quadrilateral maps on the torus and the Klein bottle. We treat the two toroidal families $Q_{k,m,r}$ and $Q_{k,m,e}$, obtained from suitable identifications of finite square grids, and, using the known isomorphisms among Klein-bottle quadrilateral maps, the three essential Klein-bottle families $Q_{k,m,a}$, $Q_{k,m,b}$, and $Q_{k,m,h}$. The ${\ell }_1$-embeddable toroidal maps are exactly $Q_{k,m,0},Q_{k,2,1},Q_{k,1,e},Q_{5,2,e},Q_{2i,2,e}(i\ge 2)$, and the ${\ell }_1$-embeddable Klein-bottle maps are exactly $Q_{2,2,a},Q_{4,2,a},Q_{2,m,b},Q_{1,2,h}.$ All other members of these five families are not ${\ell }_1$-embeddable.

arXiv comment17 pages