In graph theory, a strong orientation of an undirected graph is an assignment of a direction to each edge (an orientation) that makes it into a strongly connected graph. Strong orientations have been applied to the design of one-way road networks. According to Robbins' theorem, the graphs with strong orientations are exactly the bridgeless graphs, or equivalently, graphs in which each connected component is 2-edge-connected. Eulerian orientations and well-balanced orientations provide important special cases of strong orientations; in turn, strong orientations may be generalized to totally cyclic orientations of disconnected graphs. The set of strong orientations of a graph forms a partial cube, with adjacent orientations in this structure differing in the orientation of a single edge. It is possible to find a single orientation in linear time, but it is #P-complete to count the number of strong orientations of a given graph.
Application to traffic control Robbins (1939) introduces the problem of strong orientation with a story about a town, whose streets and intersections are represented by the given graph G. According to Robbins' story, the people of the town want to be able to repair any segment of road during the weekdays, while still allowing any part of the town to be reached from any other part using the remaining roads as two-way streets. On the weekends, all roads are open, but because of heavy traffic volume, they wish to convert all roads to one-way streets and again allow any part of town to be reached from any other part. Robbins' theorem states that a system of roads is suitable for weekday repairs if and only if it is suitable for conversion to a one-way system on weekends. For this reason, his result is sometimes known as the one-way street theorem. 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.
Related types of orientation If an undirected graph has an Euler tour, an Eulerian orientation of the graph (an orientation for which every vertex has indegree equal to its outdegree) may be found by orienting the edges consistently around the tour. These orientations are automatically strong orientations. A theorem of Nash-Williams (1960, 1969) states that every undirected graph G has a well-balanced orientation. This is an orientation with the property that, for every pair of vertices u and v in G, the number of pairwise edge-disjoint directed paths from u to v in the resulting directed graph is at least ⌊ k / 2 ⌋ {\displaystyle \left\lfloor k/2\right\rfloor } , where k is the maximum number of paths in a set of edge-disjoint undirected paths from u to v. Nash-Williams' orientations also have the property that they are as close as possible to being Eulerian orientations: at each vertex, the indegree and the outdegree are within one of each other. The existence of well-balanced orientations, together with Menger's theorem, immediately implies Robbins' theorem: by Menger's theorem, a 2-edge-connected graph has at least two edge-disjoint paths between every pair of vertices, from which it follows that any well-balanced orientation must be strongly connected. More generally this result implies that every 2k-edge-connected undirected graph can be oriented to form a k-edge-connected directed graph. A totally cyclic orientation of a graph G is an orientation in which each edge belongs to a directed cycle. For connected graphs, this is the same thing as a strong orientation, but totally cyclic orientations may also be defined for disconnected graphs, and are the orientations in which each connected component of G becomes strongly connected. 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. Totally cyclic orientations are dual to acyclic orientations (orientations that turn G into a directed acyclic graph) in the sense that, if G is a planar graph, and orientations of G are transferred to orientations of the planar dual graph of G by turning each edge 90 degrees clockwise, then a totally cyclic orientation of G corresponds in this way to an acyclic orientation of the dual graph and vice versa. The number of different totally cyclic orientations of any graph G is TG(0, 2) where TG is the Tutte polynomial of the graph, and dually the number of acyclic orientations is TG(2, 0). 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. If a strong orientation has the property that all directed cycles pass through a single edge st (equivalently, if flipping the orientation of an edge produces an acyclic orientation) then the acyclic orientation formed by reversing st is a bipolar orientation. Every bipolar orientation is related to a strong orientation in this way.
Flip graphs If G is a 3-edge-connected graph, and X and Y are any two different strong orientations of G, then it is possible to transform X into Y by changing the orientation of a single edge at a time, at each step preserving the property that the orientation is strong. Therefore, the flip graph whose vertices correspond to the strong orientations of G, and whose edges correspond to pairs of strong orientations that differ in the direction of a single edge, forms a partial cube.
… excerpt ends here. Continue reading the full article.
