1988/05/01 by Fred S. Roberts, Yonghua Xu · 1 citation
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Computational Geometry and Mesh Generation #Smart Parking Systems Research #Grid #Mathematics #Combinatorics #Alternation (linguistics) #Variety (cybernetics) #Graph #Geometry #Statistics
paper · doi:10.1137/0401022
openalex publication_date 1988/05/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/11
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 n1 + 1 east-west avenues and n2 + 1 north-south streets, for n1 ,n2 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.