The comparability graph, respectively the incomparability graph, of a poset \(P:=(V,\le )\)  is the undirected graph, denoted by \(Comp(P)\) , respectively \(Inc(P)\) , with vertex set \(V\)  and edges the pairs \(\lbrace u,v\rbrace \)  of comparable distinct vertices (that is, either \(u< v\)  or \(v<u\) ) respectively incomparable vertices. A graph \(G:= (V, E)\)  is a comparability graph if the edge set is the set of comparabilities of some order on \(V\) . From the Compactness Theorem of First Order Logic, it follows that a graph is a comparability graph iff every finite induced subgraph is a comparability graph. Hence, the class of comparability graphs is determined by a set of finite obstructions. The complete list of minimal obstructions was determined by Gallai [1]}. A graph \(G:= (V, E)\)  is a permutation graph if there is a total order \(\le \)  on \(V\)  and a permutation \(\sigma \)  of \(V\)  such that the edges of \(G\)  are the pairs \(\lbrace x, y\rbrace \in [V]^2\)  which are reversed by \(\sigma \) . Denoting by \(\le _{\sigma }\)  the set of oriented pairs \((x, y)\)  such that \(\sigma (x) \le \sigma (y)\) , the graph is the comparability graph of the poset whose order is the intersection of \(\le \)  and the opposite of \(\le _{\sigma }\) . Hence, a permutation graph is the comparability graph of an order intersection of two total orders, that is the comparability graph of an order of dimension at most two [2]}. The converse does not hold in general. It holds, if the graph is finite. As it is well known, a finite graph \(G\)  is a permutation graph iff \(G\)  and \(\overline{G}\)  are comparability graphs [2]}; in particular, a finite graph is a permutation graph if and only if its complement is a permutation graph. Via the Compactness Theorem of First Order Logic, an infinite graph is the comparability graph of a poset intersection of two total orders if an only if each finite induced graph is a permutation graph (sometimes these graphs are called permutation graphs, while there is no possible permutation involved). For more about permutation graphs, see [4]}.
