often represent a permutation graph with a *permutation diagram*, which is drawn as follows. See [ \[fig:permdia\_example1\]]{} for an illustration. Imagine two horizontal parallel lines $\ell_1$ and $\ell_2$ on the plane. Then, we place the vertices in $V$ on $\ell_1$ from left to right according to the permutation ordering $\prec_1$ as distinct points, and similarly place the vertices in $V$ on $\ell_2$ from left to right according to $\prec_2$ as distinct points. The positions of $v\in V$ can be represented by $x$-coordinates on $\ell_{1}$ and $\ell_{2}$, which are denoted by ${\mathtt{x}}_{1}(v)$ and ${\mathtt{x}}_{2}(v)$, respectively. We connect the two points representing the same vertex with a line segment. The process results in a diagram with $|V|$ line segments. By definition, $uv \in E$ if and only if the line segments representing $u$ and $v$ cross in the permutation diagram, which is equivalent to the inequality $({\mathtt{x}}_1(u)-{\mathtt{x}}_1(v)) ({\mathtt{x}}_2(u)-{\mathtt{x}}_2(v)) < 0$.

![An example of a permutation diagram. (Left) A permutation graph $G$. (Right) A permutation diagram that represents $G$.[]{data-label="fig:permdia_example1"}](\figdir/permdia_example1)

Conversely, from a permutation diagram of $G$, we can extract linear orderings $\prec_{1}$ and $\prec_{2}$ as $$\begin{aligned}
{\mathtt{x}}_1(u) < {\mathtt{x}}_1(v) &\iff& u \prec_{1} v,\\
{\mathtt{x}}_2(u) < {\mathtt{x}}_2(v) &\iff& u \prec_{2} v.\end{aligned}$$ When those conditions 