Orientation (graph theory)

Therefore, the same sequence of numbers also solves the graph enumeration problem for complete digraphs.

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 graphs with transitive orientations are called comparability graphs; they may be defined from a 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.

Eulerian orientations of grid graphs arise in statistical mechanics in the theory of ice-type models.