P = transitiveOrientation G
A transitive orientation of a graph $G$ is an orientation on the edges of $G$ such that if $a < b$ and $b < c$, then $a < c$. Not all graphs have transitive orientations, but those that do are comparabilityGraphs of posets.
|
|
A transitive orientation of a graph $G$ need not be unique. To see other random orientations, set the option Random to true.
|
|
|
If the give graph is not a comparability graph, e.g. an odd cycle of length at least $5$, then the method returns an error.
The method implemented is Algorithm 5.3 (pages 129-130) from Martin Charles Golumbic, "Algorithmic graph theory and perfect graphs." Second edition. Annals of Discrete Mathematics, 57. Elsevier Science B.V., Amsterdam, 2004. xxvi+314pp.
The object transitiveOrientation is a method function with options.