A graph is a bipartite permutation graph if and only if it is a unit interval bigraph.

The following lemma shows that a bipartite permutation graph can be represented by a permutation diagram with a special property. An illustration is given in [ \[fig:lem2-11\]]{}.

![An illustration of Lemma \[lem:rightanglerep\]. (Left) A permutation diagram of a bipartite permutation graph $G=(X,Y;E)$. The vertices in $X$ are represented by blue segments, and the vertices in $Y$ are represented by red segments. (Right) A permutation diagram that represents $G$ obtained by Lemma \[lem:rightanglerep\].[]{data-label="fig:lem2-11"}](\figdir/lem2-11)

\[lem:rightanglerep\] Let $G=(X, Y; E)$ be a bipartite permutation graph. Then, $G$ can be represented by a permutation diagram in which ${\mathtt{x}}_{2}(x)={\mathtt{x}}_{1}(x)+1$ for $x \in X$ and ${\mathtt{x}}_{2}(y)={\mathtt{x}}_{1}(y)-1$ for $y \in Y$.

By Proposition \[prop:bpg=uib\], there is a set of unit intervals $\{I_{v} = [l_{v}, l_{v}+1] \mid v \in X \cup Y\}$ such that for $x \in X$ and $y \in Y$, $xy \in E$ if and only if $I_{x} \cap I_{y} \ne \emptyset$. We can assume that all endpoints of the intervals are distinct; that is, $l_{u} \notin \{l_{v}, l_{v}+1\}$ for all $u,v \in X \cup Y $ with $u \ne v$ [@West98]. For each $x \in X$, we set 