Strong orientation

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. 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.^[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.

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.^[2] 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 $\lfloor\frac{k}{2}\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 $2 k$ -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.^[3]^[4] The number of different totally cyclic orientations of any graph $G$ is $T G (0,2)$ where $T G$ is the Tutte polynomial of the graph, and dually the number of acyclic orientations is $T G (2,0)$ .^[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.

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.^[6]

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.^[7] 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.

Algorithms and complexity

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.^[8] If an undirected graph $G$ with bridges is given, together with a list of ordered pairs of vertices that must be connected by directed paths, it is possible in polynomial time to find an orientation of $G$ that connects all the given pairs, if such an orientation exists. However, the same problem is NP-complete when the input may be a mixed graph.^[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]^[10] However, for dense graphs (more specifically, graphs in which each vertex has a linear number of neighbors), the number of strong orientations may be estimated by a fully polynomial-time randomized approximation scheme.^[3]^[11] The problem of counting strong orientations may also be solved exactly, in polynomial time, for graphs of bounded treewidth.^[3]

Notes

References

Alon, Noga; Frieze, Alan; Welsh, Dominic (1995), "Polynomial time randomized approximation schemes for Tutte-Gröthendieck invariants: the dense case", Random Structures & Algorithms 6 (4): 459–478, doi:10.1002/rsa.3240060409, MR 1368847
Arkin, Esther M.; Hassin, Refael (2002), "A note on orientations of mixed graphs", Discrete Applied Mathematics 116 (3): 271–278, doi:10.1016/S0166-218X(01)00228-1, MR 1878572 .
Atallah, Mikhail J. (1984), "Parallel strong orientation of an undirected graph", Information Processing Letters 18 (1): 37–39, doi:10.1016/0020-0190(84)90072-3, MR 742079 .
de Fraysseix, Hubert; de Mendez, Patrice Ossona; Rosenstiehl, Pierre (1995), "Bipolar orientations revisited", Discrete Applied Mathematics 56 (2-3): 157–179, doi:10.1016/0166-218X(94)00085-R, MR 1318743 .
Fukuda, Komei; Prodon, Alain; Sakuma, Tadashi (2001), "Notes on acyclic orientations and the shelling lemma", Theoretical Computer Science 263 (1-2): 9–16, doi:10.1016/S0304-3975(00)00226-7, MR 1846912 .
Koh, K. M.; Tay, E. G. (2002), "Optimal orientations of graphs and digraphs: a survey", Graphs and Combinatorics 18 (4): 745–756, doi:10.1007/s003730200060, MR 1964792 .
Las Vergnas, Michel (1980), "Convexity in oriented matroids", Journal of Combinatorial Theory, Series B 29 (2): 231–243, doi:10.1016/0095-8956(80)90082-9, MR 586435 .
Nash-Williams, C. St. J. A. (1960), "On orientations, connectivity and odd-vertex-pairings in finite graphs.", Canadian Journal of Mathematics 12: 555–567, doi:10.4153/cjm-1960-049-6, MR 0118684 .
Nash-Williams, C. St. J. A. (1969), "Well-balanced orientations of finite graphs and unobtrusive odd-vertex-pairings", Recent Progress in Combinatorics (Proc. Third Waterloo Conf. on Combinatorics, 1968), New York: Academic Press, pp. 133–149, MR 0253933 .
Noy, Marc (2001), "Acyclic and totally cyclic orientations in planar graphs", The American Mathematical Monthly 108 (1): 66–68, doi:10.2307/2695680, MR 1857074 .
Robbins, H. E. (1939), "A theorem on graphs, with an application to a problem on traffic control", American Mathematical Monthly 46: 281–283, JSTOR 2303897 .
Roberts, Fred S. (1978), "Chapter 2. The One-Way Street Problem", Graph Theory and its Applications to Problems of Society, CBMS-NSF Regional Conference Series in Applied Mathematics 29, Philadelphia, Pa.: Society for Industrial and Applied Mathematics (SIAM), pp. 7–14, MR 508050 .
Roberts, Fred S.; Xu, Yonghua (1988), "On the optimal strongly connected orientations of city street graphs. I. Large grids", SIAM Journal on Discrete Mathematics 1 (2): 199–222, doi:10.1137/0401022, MR 941351 .
Roberts, Fred S.; Xu, Yonghua (1989), "On the optimal strongly connected orientations of city street graphs. II. Two east-west avenues or north-south streets", Networks 19 (2): 221–233, doi:10.1002/net.3230190204, MR 984567 .
Roberts, Fred S.; Xu, Yonghua (1992), "On the optimal strongly connected orientations of city street graphs. III. Three east-west avenues or north-south streets", Networks 22 (2): 109–143, doi:10.1002/net.3230220202, MR 1148018 .
Roberts, Fred S.; Xu, Yong Hua (1994), "On the optimal strongly connected orientations of city street graphs. IV. Four east-west avenues or north-south streets", Discrete Applied Mathematics 49 (1-3): 331–356, doi:10.1016/0166-218X(94)90217-8, MR 1272496 .
Schrijver, A. (1983), "Bounds on the number of Eulerian orientations", Combinatorica 3 (3-4): 375–380, doi:10.1007/BF02579193, MR 729790 .
Vertigan, D. L.; Welsh, D. J. A. (1992), "The computational complexity of the Tutte plane: the bipartite case", Combinatorics, Probability and Computing 1 (2): 181–187, doi:10.1017/S0963548300000195, MR 1179248 .
Welsh, Dominic (1997), "Approximate counting", Surveys in combinatorics, 1997 (London), London Math. Soc. Lecture Note Ser. 241, Cambridge: Cambridge Univ. Press, pp. 287–323, doi:10.1017/CBO9780511662119.010, MR 1477750 .