# transitiveOrientation -- generates a poset whose comparability graph is the given graph

## Synopsis

• Usage:
P = transitiveOrientation G
• Inputs:
• G, an instance of the type Graph,
• Optional inputs:
• Random => , default value false, whether to randomise the edges first
• Strategy => , default value error, whether to throw an error ('error') if the graph has no transitive orientation or to return a null ('null')
• Outputs:

## Description

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.