Comellas, F.; Dalfó, C.; Fiol, M. A. Multidimensional Manhattan street networks. (English) Zbl 1227.05156 SIAM J. Discrete Math. 22, No. 4, 1428-1447 (2008). Summary: 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. Cited in 3 Documents MSC: 05C20 Directed graphs (digraphs), tournaments 05C25 Graphs and abstract algebra (groups, rings, fields, etc.) 05C12 Distance in graphs 05C45 Eulerian and Hamiltonian graphs 90B10 Deterministic network models in operations research Keywords:Manhattan street network; line digraph; Cayley digraph; diameter; Hamiltonian cycle PDFBibTeX XMLCite \textit{F. Comellas} et al., SIAM J. Discrete Math. 22, No. 4, 1428--1447 (2008; Zbl 1227.05156) Full Text: DOI