Multidimensional Manhattan Street Networks
Francesc Comellas, C. Dalfó, Miquel Àngel Fiol · SIAM Journal on Discrete Mathematics · 2008
We formally define the n-dimensional Manhattan street network $M_n$—a special case of an n-regular digraph—and we study some of its structural properties. In particular, we show that $M_n$ is a Cayley digraph, which can be seen as a subgroup of the n-dimensional version of the wallpaper group $pgg$. These results induce a useful new representation of $M_n$, which can be applied to design a local (shortest-path) routing algorithm and to study some other metric properties, such as the diameter. We also show that the n-dimensional Manhattan street networks are Hamiltonian and, in the standard case (that is, in dimension two), we give sufficient conditions for a 2-dimensional Manhattan street network to be decomposable into two arc-disjoint Hamiltonian cycles.