# Acyclic orientation

For planar graphs, acyclic orientations are dual to totally cyclic orientations, orientations in which each edge belongs to a directed cycle: 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. This duality extends to nonplanar graphs as well, via the Tutte polynomial $T_{G}$ of a graph $G$ , which can be used to count both types of orientations: the number of acyclic orientations of $G$ is $T_{G}(2,0)$ and the number of totally cyclic orientations is $T_{G}(0,2)$ . The number of acyclic orientations may also be counted using a different polynomial, the chromatic polynomial $\chi _{G}$ : there are $|\chi _{G}(-1)|$ different acyclic orientations. The set of all acyclic orientations of a given graph may be given the structure of a partial cube, in which two acyclic orientations are adjacent whenever they differ in the direction of a single edge.