On the Optimal Strongly Connected Orientations of City Street Graphs I: Large Grids
Fred S. Roberts, Yonghua Xu · SIAM Journal on Discrete Mathematics · 1988
The problem of finding strongly connected orientations (one-way street assignments) for graphs which arise from city streets is studied. Specifically, the grid graphs consisting of $n_1 + 1$ east-west avenues and $n_2 + 1$ north-south streets, for $n_1 ,n_2 $ sufficiently large, are studied. In general, it is difficult to find strongly connected orientations of graphs which are optimal according to any of a variety of criteria. However, for the grid graphs in question, optimal strongly connected orientations according to several important criteria are described. The results are surprising in that they improve significantly on the solution usually used in practice, namely: alternation of east and west orientations and north and south orientations.