Comparability graph

For any strict partially ordered set (S,<), the comparability graph of (S, <) is the graph (S, ⊥) of which the vertices are the elements of S and the edges are those pairs {u, v} of elements such that u < v. That is, for a partially ordered set, take the directed acyclic graph, apply transitive closure, and remove orientation.

[2] Comparability graphs can be characterized as the graphs such that, for every generalized cycle (see below) of odd length, one can find an edge (x,y) connecting two vertices that are at distance two in the cycle.

In this context, a generalized cycle is defined to be a closed walk that uses each edge of the graph at most once in each direction.

[5] Comparability graphs can also be characterized by a list of forbidden induced subgraphs.

As Seymour (2006) observes, every comparability graph that is neither complete nor bipartite has a skew partition.

[13] A transitive orientation of a graph, if it exists, can be found in linear time.

Hasse diagram of a poset (left) and its comparability graph (right)
One of the forbidden induced subgraphs of a comparability graph. The generalized cycle a–b–d–f–d–c–e–c–b–a in this graph has odd length (nine) but has no triangular chords.