Strong orientation

<h2 id="application-to-traffic-control">Application to traffic control</h2>
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. <a href="/facts/Robbins%27_theorem/QmA6Gzwj">Robbins' theorem</a> 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.<a class="footnote-ref" id="fnref:1" href="#fn:1">1</a>
Subsequently to the work of Robbins, a series of papers by Roberts and Xu modeled more carefully the problem of turning a <a href="/facts/Grid_graph/4EHMt1b6">grid</a> 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.

<h2 id="related-types-of-orientation">Related types of orientation</h2>
If an undirected graph has an <a href="/facts/Euler_tour/4l2G67c7">Euler tour</a>, 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.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a> 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 {\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 <a href="/facts/Menger%27s_theorem/NlHduKXm">Menger's theorem</a>, 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 <a href="/facts/Directed_acyclic_graph/k6zq1os9">directed acyclic graph</a>) in the sense that, if G is a <a href="/facts/Planar_graph/plREagr9">planar graph</a>, and orientations of G are transferred to orientations of the <a href="/facts/Planar_dual/1t14hhEF">planar dual</a> 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.<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a><a class="footnote-ref" id="fnref:4" href="#fn:4">4</a> The number of different totally cyclic orientations of any graph G is TG(0, 2) where TG is the <a href="/facts/Tutte_polynomial/RMzCMxTQ">Tutte polynomial</a> of the graph, and dually the number of acyclic orientations is TG(2, 0).<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a> 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 <a href="/facts/Acyclic_orientation/cdAUkyFH">acyclic orientation</a>) then the acyclic orientation formed by reversing st is a <a href="/facts/Bipolar_orientation/TSb4PyzJ">bipolar orientation</a>. Every bipolar orientation is related to a strong orientation in this way.<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a>

<h2 id="flip-graphs">Flip graphs</h2>
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.<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a> Therefore, the <a href="/facts/Flip_graph/X7r9D8jx">flip graph</a> 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 <a href="/facts/Partial_cube/B0yHINHS">partial cube</a>.

<h2 id="algorithms-and-complexity">Algorithms and complexity</h2>
A strong orientation of a given bridgeless undirected graph may be found in <a href="/facts/Linear_time/77T62gmf">linear time</a> by performing a <a href="/facts/Depth-first_search/luxJKVph">depth-first search</a> 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.<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a> 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 <a href="/facts/Polynomial_time/77T62gmf">polynomial time</a> to find an orientation of G that connects all the given pairs, if such an orientation exists. However, the same problem is <a href="/facts/NP-complete/NFPv56DU">NP-complete</a> when the input may be a mixed graph.<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a>
It is <a href="/facts/Sharp-P-complete/M6QgPJY6">#P-complete</a> to count the number of strong orientations of a given graph G, even when G is planar and <a href="/facts/Bipartite_graph/xWcXV9MB">bipartite</a>.<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a><a class="footnote-ref" id="fnref:11" href="#fn:11">11</a> However, for <a href="/facts/Dense_graph/xFC7b7s9">dense graphs</a> (more specifically, graphs in which each vertex has a linear number of neighbors), the number of strong orientations may be estimated by a <a href="/facts/Fully_polynomial-time_randomized_approximation_scheme/52Chjx9y">fully polynomial-time randomized approximation scheme</a>.<a class="footnote-ref" id="fnref:12" href="#fn:12">12</a><a class="footnote-ref" id="fnref:13" href="#fn:13">13</a> The problem of counting strong orientations may also be solved exactly, in <a href="/facts/Polynomial_time/77T62gmf">polynomial time</a>, for graphs of bounded <a href="/facts/Treewidth/uoITxzRJ">treewidth</a>.<a class="footnote-ref" id="fnref:14" href="#fn:14">14</a>

<h2 id="notes">Notes</h2>

<ul><li><a href="/facts/Noga_Alon/tuqq2GUl">Alon, Noga</a>; <a href="/facts/Alan_M._Frieze/QWsuXmRw">Frieze, Alan</a>; Welsh, Dominic (1995), "Polynomial time randomized approximation schemes for Tutte-Gröthendieck invariants: the dense case", Random Structures & Algorithms, 6 (4): 459–478, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1002%2Frsa.3240060409">10.1002/rsa.3240060409</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1368847">1368847</a></li>
<li><a href="/facts/Esther_Arkin/AdGM7tyW">Arkin, Esther M.</a>; Hassin, Refael (2002), <a href="http://www.ams.sunysb.edu/~estie/papers/new-or.pdf">"A note on orientations of mixed graphs"</a> (PDF), Discrete Applied Mathematics, 116 (3): 271–278, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2FS0166-218X%2801%2900228-1">10.1016/S0166-218X(01)00228-1</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1878572">1878572</a>.</li>
<li><a href="/facts/Mikhail_Atallah/Sf1W79uX">Atallah, Mikhail J.</a> (1984), <a href="https://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1361&context=cstech">"Parallel strong orientation of an undirected graph"</a>, <a href="/facts/Information_Processing_Letters/e2u7fEKe">Information Processing Letters</a>, 18 (1): 37–39, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2F0020-0190%2884%2990072-3">10.1016/0020-0190(84)90072-3</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0742079">0742079</a>.</li>
<li>de Fraysseix, Hubert; <a href="/facts/Patrice_Ossona_de_Mendez/UdmKUVR7">Ossona de Mendez, Patrice</a>; <a href="/facts/Rosenstiehl/0m4GAfVp">Rosenstiehl, Pierre</a> (1995), "Bipolar orientations revisited", Discrete Applied Mathematics, 56 (2–3): 157–179, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2F0166-218X%2894%2900085-R">10.1016/0166-218X(94)00085-R</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1318743">1318743</a>.</li>
<li><a href="/facts/Komei_Fukuda/H88HI0Q4">Fukuda, Komei</a>; Prodon, Alain; Sakuma, Tadashi (2001), <a href="https://www.cs.mcgill.ca/~fukuda/download/paper/acyclic980112.ps.gz">"Notes on acyclic orientations and the shelling lemma"</a>, Theoretical Computer Science, 263 (1–2): 9–16, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2FS0304-3975%2800%2900226-7">10.1016/S0304-3975(00)00226-7</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1846912">1846912</a></li>
<li>Koh, K. M.; Tay, E. G. (2002), "Optimal orientations of graphs and digraphs: a survey", <a href="/facts/Graphs_and_Combinatorics/kQJQ9uUy">Graphs and Combinatorics</a>, 18 (4): 745–756, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2Fs003730200060">10.1007/s003730200060</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1964792">1964792</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:34821155">34821155</a>.</li>
<li><a href="/facts/Michel_Las_Vergnas/BwzovsQd">Las Vergnas, Michel</a> (1980), "Convexity in oriented matroids", <a href="/facts/Journal_of_Combinatorial_Theory/oYS6G76K">Journal of Combinatorial Theory</a>, Series B, 29 (2): 231–243, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2F0095-8956%2880%2990082-9">10.1016/0095-8956(80)90082-9</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0586435">0586435</a>.</li>
<li><a href="/facts/Crispin_Nash-Williams/YY5uresp">Nash-Williams, C. St. J. A.</a> (1960), "On orientations, connectivity and odd-vertex-pairings in finite graphs.", Canadian Journal of Mathematics, 12: 555–567, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.4153%2Fcjm-1960-049-6">10.4153/cjm-1960-049-6</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0118684">0118684</a>.</li>
<li><a href="/facts/Crispin_Nash-Williams/YY5uresp">Nash-Williams, C. St. J. A.</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, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0253933">0253933</a>.</li>
<li>Noy, Marc (2001), "Acyclic and totally cyclic orientations in planar graphs", <a href="/facts/The_American_Mathematical_Monthly/Te6CHvkg">The American Mathematical Monthly</a>, 108 (1): 66–68, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.2307%2F2695680">10.2307/2695680</a>, <a href="/facts/JSTOR_(identifier)/YTeVmaJ7">JSTOR</a> <a href="https://www.jstor.org/stable/2695680">2695680</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1857074">1857074</a>.</li>
<li><a href="/facts/Herbert_Robbins/Gk2X6ap9">Robbins, H. E.</a> (1939), "A theorem on graphs, with an application to a problem on traffic control", <a href="/facts/American_Mathematical_Monthly/Te6CHvkg">American Mathematical Monthly</a>, 46 (5): 281–283, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.2307%2F2303897">10.2307/2303897</a>, <a href="/facts/JSTOR_(identifier)/YTeVmaJ7">JSTOR</a> <a href="https://www.jstor.org/stable/2303897">2303897</a>.</li>
<li><a href="/facts/Fred_S._Roberts/Ql0DSQJk">Roberts, Fred S.</a> (1978), "Chapter 2. The One-Way Street Problem", <a href="https://books.google.com/books?id=EYAwztXnzf8C&pg=PA7">Graph Theory and its Applications to Problems of Society</a>, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 29, Philadelphia, Pa.: Society for Industrial and Applied Mathematics (SIAM), pp. 7–14, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 9780898710267, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0508050">0508050</a>.</li>
<li>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, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1137%2F0401022">10.1137/0401022</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0941351">0941351</a>.</li>
<li>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, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1002%2Fnet.3230190204">10.1002/net.3230190204</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0984567">0984567</a>.</li>
<li>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, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1002%2Fnet.3230220202">10.1002/net.3230220202</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1148018">1148018</a>.</li>
<li>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, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2F0166-218X%2894%2990217-8">10.1016/0166-218X(94)90217-8</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1272496">1272496</a>.</li>
<li><a href="/facts/Alexander_Schrijver/eJHJNRGz">Schrijver, A.</a> (1983), <a href="https://ir.cwi.nl/pub/10053/10053D.pdf">"Bounds on the number of Eulerian orientations"</a> (PDF), Combinatorica, 3 (3–4): 375–380, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2FBF02579193">10.1007/BF02579193</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0729790">0729790</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:13708977">13708977</a>.</li>
<li>Vertigan, D. L.; Welsh, D. J. A. (1992), "The computational complexity of the Tutte plane: the bipartite case", <a href="/facts/Combinatorics,_Probability_and_Computing/lyqhr4XT">Combinatorics, Probability and Computing</a>, 1 (2): 181–187, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1017%2FS0963548300000195">10.1017/S0963548300000195</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1179248">1179248</a>.</li>
<li>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, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1017%2FCBO9780511662119.010">10.1017/CBO9780511662119.010</a>, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-521-59840-8, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1477750">1477750</a>.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Koh & Tay (2002). - 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 <a href="https://doi.org/10.1007%2Fs003730200060" target="_blank">https://doi.org/10.1007%2Fs003730200060</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Schrijver (1983). - 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 <a href="https://ir.cwi.nl/pub/10053/10053D.pdf" target="_blank">https://ir.cwi.nl/pub/10053/10053D.pdf</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Welsh (1997). - 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 <a href="https://doi.org/10.1017%2FCBO9780511662119.010" target="_blank">https://doi.org/10.1017%2FCBO9780511662119.010</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Noy (2001). - 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 <a href="https://doi.org/10.2307%2F2695680" target="_blank">https://doi.org/10.2307%2F2695680</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Las Vergnas (1980). - 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 <a href="https://doi.org/10.1016%2F0095-8956%2880%2990082-9" target="_blank">https://doi.org/10.1016%2F0095-8956%2880%2990082-9</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">de Fraysseix, Ossona de Mendez & Rosenstiehl (1995). - 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 <a href="https://doi.org/10.1016%2F0166-218X%2894%2900085-R" target="_blank">https://doi.org/10.1016%2F0166-218X%2894%2900085-R</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Fukuda, Prodon & Sakuma (2001). - 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 <a href="https://www.cs.mcgill.ca/~fukuda/download/paper/acyclic980112.ps.gz" target="_blank">https://www.cs.mcgill.ca/~fukuda/download/paper/acyclic980112.ps.gz</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">See e.g. Atallah (1984) and Roberts (1978). - 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 <a href="https://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1361&context=cstech" target="_blank">https://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1361&context=cstech</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Arkin & Hassin (2002). - 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 <a href="http://www.ams.sunysb.edu/~estie/papers/new-or.pdf" target="_blank">http://www.ams.sunysb.edu/~estie/papers/new-or.pdf</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Welsh (1997). - 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 <a href="https://doi.org/10.1017%2FCBO9780511662119.010" target="_blank">https://doi.org/10.1017%2FCBO9780511662119.010</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Vertigan & Welsh (1992). - 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 <a href="https://doi.org/10.1017%2FS0963548300000195" target="_blank">https://doi.org/10.1017%2FS0963548300000195</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">Welsh (1997). - 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 <a href="https://doi.org/10.1017%2FCBO9780511662119.010" target="_blank">https://doi.org/10.1017%2FCBO9780511662119.010</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn:13">Alon, Frieze & Welsh (1995). - 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 <a href="https://doi.org/10.1002%2Frsa.3240060409" target="_blank">https://doi.org/10.1002%2Frsa.3240060409</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></li>
<li id="fn:14">Welsh (1997). - 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 <a href="https://doi.org/10.1017%2FCBO9780511662119.010" target="_blank">https://doi.org/10.1017%2FCBO9780511662119.010</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></li>
</ol>

Strong orientation open-in-new

Strong orientation