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.
i1 : G = graph {{1,2}, {2,3}, {3,4}, {1,4}}; |
i2 : transitiveOrientation G o2 = Relation Matrix: | 1 1 1 0 | | 0 1 0 0 | | 0 0 1 0 | | 0 1 1 1 | o2 : Poset |
A transitive orientation of a graph $G$ need not be unique. To see other random orientations, set the option Random to true.
i3 : setRandomSeed 0; |
i4 : G = graph {{1,2},{2,3},{3,4},{1,3},{1,3}}; |
i5 : removeIsomorphicPosets apply(4, i -> transitiveOrientation(G, Random => true)) o5 = {Relation Matrix: | 1 1 1 1 |, Relation Matrix: | 1 1 0 1 |} | 0 1 1 0 | | 0 1 0 1 | | 0 0 1 0 | | 0 0 1 1 | | 0 0 0 1 | | 0 0 0 1 | o5 : List |
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.