Strong orientation

[1] Subsequently to the work of Robbins, a series of papers by Roberts and Xu modeled more carefully the problem of turning a grid of two-way city streets into one-way streets, and examined the effect of this conversion on the distances between pairs of points within the grid.

As they showed, the traditional one-way layout in which parallel streets alternate in direction is not optimal in keeping the pairwise distances as small as possible.

However, the improved orientations that they found include points where the traffic from two one-way blocks meets itself head-on, which may be viewed as a flaw in their solutions.

Robbins' theorem can be restated as saying that a graph has a totally cyclic orientation if and only if it does not have a bridge.

[5] As a consequence, Robbins' theorem implies that the Tutte polynomial has a root at the point (0,2) if and only if the graph G has a bridge.

A strong orientation of a given bridgeless undirected graph may be found in linear time by performing a depth-first search of the graph, orienting all edges in the depth-first search tree away from the tree root, and orienting all the remaining edges (which must necessarily connect an ancestor and a descendant in the depth-first search tree) from the descendant to the ancestor.

[9] It is #P-complete to count the number of strong orientations of a given graph G, even when G is planar and bipartite.

[3][11] The problem of counting strong orientations may also be solved exactly, in polynomial time, for graphs of bounded treewidth.