×

Multidimensional Manhattan street networks. (English) Zbl 1227.05156

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.

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
PDFBibTeX XMLCite
Full Text: DOI