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

Synopsis

Usage:
P = transitiveOrientation G
Inputs:
- G, an object of class Graph
Optional inputs:
- Random => a Boolean value, default value false, whether to randomise the edges first
Outputs:
- P, an object of class Poset, such that comparabilityGraph P is isomorphic to G

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 = Poset{cache => CacheTable{}                        }
           GroundSet => {1, 4, 2, 3}
           RelationMatrix => | 1 1 1 0 |
                             | 0 1 0 0 |
                             | 0 0 1 0 |
                             | 0 1 1 1 |
           Relations => {{1, 4}, {1, 2}, {3, 4}, {3, 2}}

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 = {Poset{cache => CacheTable{...1...}                 },
            GroundSet => {3, 1, 2, 4}                      
            RelationMatrix => | 1 1 1 1 |                  
                              | 0 1 0 0 |                  
                              | 0 1 1 0 |                  
                              | 0 0 0 1 |                  
            Relations => {{3, 1}, {3, 2}, {2, 1}, {3, 4}}  
     ------------------------------------------------------------------------
     Poset{cache => CacheTable{...1...}                 }}
           GroundSet => {2, 3, 4, 1}
           RelationMatrix => | 1 1 0 1 |
                             | 0 1 0 0 |
                             | 0 1 1 0 |
                             | 0 1 0 1 |
           Relations => {{2, 3}, {4, 3}, {2, 1}, {1, 3}}

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.

Caveat

This method is recursive. If the number of edges of G is large relative to the recursionLimit, then the method will throw an error.

Ways to use `transitiveOrientation` :

transitiveOrientation(Graph)

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

Synopsis

Description

Caveat

See also

Ways to use transitiveOrientation :

Ways to use `transitiveOrientation` :