# Orientation (graph theory)

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Orientation_(graph_theory)
> Markdown URL: https://mediated.wiki/source/Orientation_(graph_theory).md
> Source: https://en.wikipedia.org/wiki/Orientation_(graph_theory)
> Source revision: 1337510378
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

Assigning directions to the edges of an undirected graph

The [directed graph](/source/Directed_graph) (or digraph) on the right is an orientation of the undirected graph on the left

In [graph theory](/source/Graph_theory), an **orientation** of an [undirected graph](/source/Undirected_graph) is an assignment of a direction to each edge, turning the initial graph into a [directed graph](/source/Directed_graph).

## Oriented graphs

A directed graph is called an **oriented graph** if none of its pairs of vertices is linked by two mutually symmetric edges. Among directed graphs, the oriented graphs are the ones that have no 2-cycles (that is at most one of (*x*, *y*) and (*y*, *x*) may be arrows of the graph).[1]

A [tournament](/source/Tournament_(graph_theory)) is an orientation of a [complete graph](/source/Complete_graph). A [polytree](/source/Polytree) is an orientation of an undirected [tree](/source/Tree_(graph_theory)).[2] [Sumner's conjecture](/source/Sumner's_conjecture) states that every tournament with 2*n* − 2 vertices contains every polytree with n vertices.[3]

The number of [non-isomorphic](/source/Graph_isomorphism) oriented graphs with n vertices (for *n* = 1, 2, 3, …) is

- 1, 2, 7, 42, 582, 21480, 2142288, 575016219, 415939243032, … (sequence [A001174](https://oeis.org/A001174) in the [OEIS](/source/On-Line_Encyclopedia_of_Integer_Sequences)).

Tournaments are in one-to-one correspondence with complete directed graphs (graphs in which there is a directed edge in one or both directions between every pair of distinct vertices). A complete directed graph can be converted to an oriented graph by removing every 2-cycle, and conversely an oriented graph can be converted to a complete directed graph by adding a 2-cycle between every pair of vertices that are not endpoints of an edge; these correspondences are [bijective](/source/Bijection). Therefore, the same sequence of numbers also solves the [graph enumeration](/source/Graph_enumeration) problem for complete digraphs. There is an explicit but complicated formula for the numbers in this sequence.[4]

## Constrained orientations

A [strong orientation](/source/Strong_orientation) is an orientation that results in a [strongly connected graph](/source/Strongly_connected_graph). The closely related totally cyclic orientations are orientations in which every edge belongs to at least one simple cycle. An orientation of an undirected graph G is totally cyclic if and only if it is a strong orientation of every [connected component](/source/Connected_component_(graph_theory)) of G. [Robbins' theorem](/source/Robbins'_theorem) states that a graph has a strong orientation if and only if it is [2-edge-connected](/source/K-edge-connected_graph); disconnected graphs may have totally cyclic orientations, but only if they have no [bridges](/source/Bridge_(graph_theory)).[5]

An [acyclic orientation](/source/Acyclic_orientation) is an orientation that results in a [directed acyclic graph](/source/Directed_acyclic_graph). Every graph has an acyclic orientation; all acyclic orientations may be obtained by placing the vertices into a sequence, and then directing each edge from the earlier of its endpoints in the sequence to the later endpoint. The [Gallai–Hasse–Roy–Vitaver theorem](/source/Gallai%E2%80%93Hasse%E2%80%93Roy%E2%80%93Vitaver_theorem) states that a graph has an acyclic orientation in which the longest path has at most k vertices if and only if it can be [colored](/source/Graph_coloring) with at most k colors.[6] Acyclic orientations and totally cyclic orientations are related to each other by [planar duality](/source/Planar_dual). An acyclic orientation with a single source and a single sink is called a [bipolar orientation](/source/Bipolar_orientation).[7]

A [transitive orientation](/source/Transitive_orientation) is an orientation such that the resulting directed graph is its own [transitive closure](/source/Transitive_closure). The graphs with transitive orientations are called [comparability graphs](/source/Comparability_graph); they may be defined from a [partially ordered set](/source/Partially_ordered_set) by making two elements adjacent whenever they are comparable in the partial order.[8] A transitive orientation, if one exists, can be found in linear time.[9] However, testing whether the resulting orientation (or any given orientation) is actually transitive requires more time, as it is equivalent in complexity to [matrix multiplication](/source/Matrix_multiplication).

An [Eulerian orientation](/source/Eulerian_path) of an undirected graph is an orientation in which each vertex has equal in-degree and out-degree. Eulerian orientations of [grid graphs](/source/Grid_graph) arise in [statistical mechanics](/source/Statistical_mechanics) in the theory of [ice-type models](/source/Ice-type_model).[10]

A [Pfaffian orientation](/source/Pfaffian_orientation) has the property that certain even-length cycles in the graph have an odd number of edges oriented in each of the two directions around the cycle. They always exist for [planar graphs](/source/Planar_graph), but not for certain other graphs. They are used in the [FKT algorithm](/source/FKT_algorithm) for counting perfect matchings.[11]

## See also

- [Connex relation](/source/Connex_relation)

## References

1. **[^](#cite_ref-1)** Diestel, Reinhard (2005), "1.10 Other notions of graphs", [*Graph Theory*](http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/preview/Ch1.pdf) (PDF) (3rd ed.), [Springer](/source/Springer_Science%2BBusiness_Media), [ISBN](/source/ISBN_(identifier)) [978-3-540-26182-7](https://en.wikipedia.org/wiki/Special:BookSources/978-3-540-26182-7).

1. **[^](#cite_ref-2)** Rebane, George; [Pearl, Judea](/source/Judea_Pearl) (1987), "The recovery of causal poly-trees from statistical data", *Proc. 3rd Annual Conference on Uncertainty in Artificial Intelligence (UAI 1987), Seattle, WA, USA, July 1987*, pp. 222–228, [arXiv](/source/ArXiv_(identifier)):[1304.2736](https://arxiv.org/abs/1304.2736).

1. **[^](#cite_ref-3)** [Sumner's Universal Tournament Conjecture](http://www.math.uiuc.edu/~west/openp/univtourn.html), Douglas B. West, retrieved 2012-08-02.

1. **[^](#cite_ref-4)** [Harary, Frank](/source/Frank_Harary); Palmer, Edgar M. (1973), "Formula 5.4.13", *Graphical Enumeration*, New York: Academic Press, p. 133, [MR](/source/MR_(identifier)) [0357214](https://mathscinet.ams.org/mathscinet-getitem?mr=0357214).

1. **[^](#cite_ref-5)** [Robbins, H. E.](/source/Herbert_Robbins) (1939), "A theorem on graphs, with an application to a problem of traffic control", *[The American Mathematical Monthly](/source/The_American_Mathematical_Monthly)*, **46** (5): 281–283, [doi](/source/Doi_(identifier)):[10.2307/2303897](https://doi.org/10.2307%2F2303897), [hdl](/source/Hdl_(identifier)):[10338.dmlcz/101517](https://hdl.handle.net/10338.dmlcz%2F101517), [JSTOR](/source/JSTOR_(identifier)) [2303897](https://www.jstor.org/stable/2303897).

1. **[^](#cite_ref-6)** [Nešetřil, Jaroslav](/source/Jaroslav_Ne%C5%A1et%C5%99il); [Ossona de Mendez, Patrice](/source/Patrice_Ossona_de_Mendez) (2012), "Theorem 3.13", *Sparsity: Graphs, Structures, and Algorithms*, Algorithms and Combinatorics, vol. 28, Heidelberg: Springer, p. 42, [doi](/source/Doi_(identifier)):[10.1007/978-3-642-27875-4](https://doi.org/10.1007%2F978-3-642-27875-4), [ISBN](/source/ISBN_(identifier)) [978-3-642-27874-7](https://en.wikipedia.org/wiki/Special:BookSources/978-3-642-27874-7), [MR](/source/MR_(identifier)) [2920058](https://mathscinet.ams.org/mathscinet-getitem?mr=2920058).

1. **[^](#cite_ref-7)** de Fraysseix, Hubert; [Ossona de Mendez, Patrice](/source/Patrice_Ossona_de_Mendez); [Rosenstiehl, Pierre](/source/Rosenstiehl) (1995), "Bipolar orientations revisited", *Discrete Applied Mathematics*, **56** (2–3): 157–179, [doi](/source/Doi_(identifier)):[10.1016/0166-218X(94)00085-R](https://doi.org/10.1016%2F0166-218X%2894%2900085-R), [MR](/source/MR_(identifier)) [1318743](https://mathscinet.ams.org/mathscinet-getitem?mr=1318743).

1. **[^](#cite_ref-8)** Ghouila-Houri, Alain (1962), "Caractérisation des graphes non orientés dont on peut orienter les arrêtes de manière à obtenir le graphe d'une relation d'ordre", *[Les Comptes rendus de l'Académie des sciences](/source/Les_Comptes_rendus_de_l'Acad%C3%A9mie_des_sciences)*, **254**: 1370–1371, [MR](/source/MR_(identifier)) [0172275](https://mathscinet.ams.org/mathscinet-getitem?mr=0172275).

1. **[^](#cite_ref-9)** McConnell, R. M.; Spinrad, J. (1997), "Linear-time transitive orientation", *8th ACM-SIAM Symposium on Discrete Algorithms*, pp. 19–25.

1. **[^](#cite_ref-10)** Mihail, M.; [Winkler, P.](/source/Peter_Winkler) (1996), "On the number of Eulerian orientations of a graph", *[Algorithmica](/source/Algorithmica)*, **16** (4–5): 402–414, [doi](/source/Doi_(identifier)):[10.1007/s004539900057](https://doi.org/10.1007%2Fs004539900057), [MR](/source/MR_(identifier)) [1407581](https://mathscinet.ams.org/mathscinet-getitem?mr=1407581).

1. **[^](#cite_ref-11)** [Thomas, Robin](/source/Robin_Thomas_(mathematician)) (2006), ["A survey of Pfaffian orientations of graphs"](http://people.math.gatech.edu/~thomas/PAP/pfafsurv.pdf) (PDF), *International Congress of Mathematicians. Vol. III*, vol. 3, Eur. Math. Soc., Zürich, pp. 963–984, [doi](/source/Doi_(identifier)):[10.4171/022-3/47](https://doi.org/10.4171%2F022-3%2F47), [ISBN](/source/ISBN_(identifier)) [978-3-03719-022-7](https://en.wikipedia.org/wiki/Special:BookSources/978-3-03719-022-7), [MR](/source/MR_(identifier)) [2275714](https://mathscinet.ams.org/mathscinet-getitem?mr=2275714)

## External links

- [Weisstein, Eric W.](/source/Eric_W._Weisstein), ["Graph Orientation"](https://mathworld.wolfram.com/GraphOrientation.html), *[MathWorld](/source/MathWorld)*

- [Weisstein, Eric W.](/source/Eric_W._Weisstein), ["Oriented Graph"](https://mathworld.wolfram.com/OrientedGraph.html), *[MathWorld](/source/MathWorld)*

---
Adapted from the Wikipedia article [Orientation (graph theory)](https://en.wikipedia.org/wiki/Orientation_(graph_theory)) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Orientation_(graph_theory)?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.