${\mathtt{x}}_{1}(x) = l_{x}$ and ${\mathtt{x}}_{2}(x) = l_{x} + 1$. For each $y \in Y$, we set ${\mathtt{x}}_{1}(y) = l_{y}+1$ and ${\mathtt{x}}_{2}(y) = l_{y}$. It suffices to show that this permutation diagram represents $G$. Observe that line segments corresponding to vertices from the same set, $X$ or $Y$, are parallel and thus do not cross. For $x \in X$ and $y \in Y$, we have $$\begin{aligned}
  I_{x} \cap I_{y} \ne \emptyset
  &\iff
  |l_{x} - l_{y}| < 1 && (\because \text{ all endpoints are distinct})
  \\
  &\iff
  l_{x} < l_{y} + 1 \textrm{ and } l_{y} < l_{x} + 1
  \\
  &\iff
  {\mathtt{x}}_{1}(x) < {\mathtt{x}}_{1}(y) \textrm{ and } {\mathtt{x}}_{2}(y) < {\mathtt{x}}_{2}(x) && (\because x \in X, \  y \in Y)
  \\
  &\iff
  ({\mathtt{x}}_{1}(x)-{\mathtt{x}}_{1}(y)) ({\mathtt{x}}_{2}(x)-{\mathtt{x}}_{2}(y)) < 0.\end{aligned}$$ To see the last equivalence, observe that ${\mathtt{x}}_{1}(x) < {\mathtt{x}}_{2}(x)$ and ${\mathtt{x}}_{2}(y) < {\mathtt{x}}_{1}(y)$, and thus it is impossible to have both ${\mathtt{x}}_1(x) > {\mathtt{x}}_1(y)$ and ${\mathtt{x}}_2(y) > {\mathtt{x}}_2(x)$. Therefore, we conclude that the diagram represents $G$.

We can show that given a permutation ordering, there exists a permutation diagram consistent with the ordering that satisfies the conditions in Lemma \[lem:rightanglerep\].

\[cor:rightanglerep\] Let $G=(X, Y; E)$ be a connected bipartite permutation graph defined by permutation orderings 