Strong orientation

Last updated July 06, 2024

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 $\left\lfloor {\frac {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 $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]

Related Research Articles

In graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one path, or equivalently a connected acyclic undirected graph. A forest is an undirected graph in which any two vertices are connected by at most one path, or equivalently an acyclic undirected graph, or equivalently a disjoint union of trees.

In graph theory, a cycle in a graph is a non-empty trail in which only the first and last vertices are equal. A directed cycle in a directed graph is a non-empty directed trail in which only the first and last vertices are equal.

In graph theory, a branch of mathematics and computer science, Guan's route problem, the Chinese postman problem, postman tour or route inspection problem is to find a shortest closed path or circuit that visits every edge of an (connected) undirected graph at least once. When the graph has an Eulerian circuit, that circuit is an optimal solution. Otherwise, the optimization problem is to find the smallest number of graph edges to duplicate so that the resulting multigraph does have an Eulerian circuit. It can be solved in polynomial time, unlike the Travelling Salesman Problem which is NP-hard. It is different from the Travelling Salesman Problem in that the travelling salesman cannot repeat visited nodes.

<span class="mw-page-title-main">Hamiltonian path</span> Path in a graph that visits each vertex exactly once

In the mathematical field of graph theory, a Hamiltonian path is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle is a cycle that visits each vertex exactly once. A Hamiltonian path that starts and ends at adjacent vertices can be completed by adding one more edge to form a Hamiltonian cycle, and removing any edge from a Hamiltonian cycle produces a Hamiltonian path. The computational problems of determining whether such paths and cycles exist in graphs are NP-complete; see Hamiltonian path problem for details.

In graph theory, a branch of mathematics, the (binary) cycle space of an undirected graph is the set of its even-degree subgraphs.

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

In graph theory, an Eulerian trail is a trail in a finite graph that visits every edge exactly once. Similarly, an Eulerian circuit or Eulerian cycle is an Eulerian trail that starts and ends on the same vertex. They were first discussed by Leonhard Euler while solving the famous Seven Bridges of Königsberg problem in 1736. The problem can be stated mathematically like this:

In the mathematical field of graph theory, a spanning treeT of an undirected graph G is a subgraph that is a tree which includes all of the vertices of G. In general, a graph may have several spanning trees, but a graph that is not connected will not contain a spanning tree. If all of the edges of G are also edges of a spanning tree T of G, then G is a tree and is identical to T.

In graph theory, a proper edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several different types of graph coloring. The edge-coloring problem asks whether it is possible to color the edges of a given graph using at most $k$ different colors, for a given value of $k$ , or with the fewest possible colors. The minimum required number of colors for the edges of a given graph is called the chromatic index of the graph. For example, the edges of the graph in the illustration can be colored by three colors but cannot be colored by two colors, so the graph shown has chromatic index three.

In graph theory, a part of discrete mathematics, the BEST theorem gives a product formula for the number of Eulerian circuits in directed (oriented) graphs. The name is an acronym of the names of people who discovered it: N. G. de Bruijn, Tatyana Ehrenfest, Cedric Smith and W. T. Tutte.

In graph theory and graph algorithms, a feedback arc set or feedback edge set in a directed graph is a subset of the edges of the graph that contains at least one edge out of every cycle in the graph. Removing these edges from the graph breaks all of the cycles, producing an acyclic subgraph of the given graph, often called a directed acyclic graph. A feedback arc set with the fewest possible edges is a minimum feedback arc set and its removal leaves a maximum acyclic subgraph; weighted versions of these optimization problems are also used. If a feedback arc set is minimal, meaning that removing any edge from it produces a subset that is not a feedback arc set, then it has an additional property: reversing all of its edges, rather than removing them, produces a directed acyclic graph.

In the mathematical discipline of graph theory, the dual graph of a planar graph $G$ is a graph that has a vertex for each face of $G$ . The dual graph has an edge for each pair of faces in $G$ that are separated from each other by an edge, and a self-loop when the same face appears on both sides of an edge. Thus, each edge $e$ of $G$ has a corresponding dual edge, whose endpoints are the dual vertices corresponding to the faces on either side of $e$ . The definition of the dual depends on the choice of embedding of the graph $G$ , so it is a property of plane graphs rather than planar graphs. For planar graphs generally, there may be multiple dual graphs, depending on the choice of planar embedding of the graph.

The Tutte polynomial, also called the dichromate or the Tutte–Whitney polynomial, is a graph polynomial. It is a polynomial in two variables which plays an important role in graph theory. It is defined for every undirected graph $and contains information about how the graph is connected. It is denoted by .$

In graph theory, a comparability graph is an undirected graph that connects pairs of elements that are comparable to each other in a partial order. Comparability graphs have also been called transitively orientable graphs, partially orderable graphs, containment graphs, and divisor graphs. An incomparability graph is an undirected graph that connects pairs of elements that are not comparable to each other in a partial order.

In graph theory, a nowhere-zero flow or NZ flow is a network flow that is nowhere zero. It is intimately connected to coloring planar graphs.

In graph theory, a branch of mathematics, a skew-symmetric graph is a directed graph that is isomorphic to its own transpose graph, the graph formed by reversing all of its edges, under an isomorphism that is an involution without any fixed points. Skew-symmetric graphs are identical to the double covering graphs of bidirected graphs.

In graph theory, an orientation of an undirected graph is an assignment of a direction to each edge, turning the initial graph into a directed graph.

In graph theory, an acyclic orientation of an undirected graph is an assignment of a direction to each edge that does not form any directed cycle and therefore makes it into a directed acyclic graph. Every graph has an acyclic orientation.

In graph theory, the Gallai–Hasse–Roy–Vitaver theorem is a form of duality between the colorings of the vertices of a given undirected graph and the orientations of its edges. It states that the minimum number of colors needed to properly color any graph $equals one plus the length of a longest path in an orientation of chosen to minimize this path's length. The orientations for which the longest path has minimum length always include at least one acyclic orientation.$

In graph theory, Robbins' theorem, named after Herbert Robbins, states that the graphs that have strong orientations are exactly the 2-edge-connected graphs. That is, it is possible to choose a direction for each edge of an undirected graph $G$ , turning it into a directed graph that has a path from every vertex to every other vertex, if and only if $G$ is connected and has no bridge.

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" (PDF), 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 0742079 .
de Fraysseix, Hubert; Ossona de Mendez, Patrice; 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, S2CID 34821155 .
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 0586435 .
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, JSTOR 2695680, MR 1857074 .
Robbins, H. E. (1939), "A theorem on graphs, with an application to a problem on traffic control", American Mathematical Monthly , 46 (5): 281–283, doi:10.2307/2303897, 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, vol. 29, Philadelphia, Pa.: Society for Industrial and Applied Mathematics (SIAM), pp. 7–14, ISBN 9780898710267, MR 0508050 .
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 0941351 .
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 0984567 .
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" (PDF), Combinatorica, 3 (3–4): 375–380, doi:10.1007/BF02579193, MR 0729790, S2CID 13708977 .
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., vol. 241, Cambridge: Cambridge Univ. Press, pp. 287–323, doi:10.1017/CBO9780511662119.010, ISBN 978-0-521-59840-8, MR 1477750 .

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Koh & Tay (2002).

[2] Schrijver (1983).

[w97-3] 1 2 3 4 Welsh (1997).

[4] Noy (2001).

[5] Las Vergnas (1980).

[FOOTNOTEde_FraysseixOssona_de_MendezRosenstiehl1995-6] Fraysseix, Ossona de Mendez & Rosenstiehl (1995).

[7] Fukuda, Prodon & Sakuma (2001).

[8] See e.g. Atallah (1984) and Roberts (1978).

[9] Arkin & Hassin (2002).

[10] Vertigan & Welsh (1992).

[11] Alon, Frieze & Welsh (1995).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]