are satisfied, we say that the orderings of the $x$-coordinates on $\ell_1$ and $\ell_2$ are *consistent* with the linear orderings $\prec_{1}$ and $\prec_{2}$, respectively.

A graph is a *bipartite permutation graph* if it is a bipartite graph and a permutation graph. Although a permutation graph may have an exponential number of permutation orderings, it is essentially unique for a connected bipartite permutation graph in the sense of Lemma \[lem:uniquerep\] below. For a graph $G = (V,E)$, linear orderings $\langle v_{1}, \dots, v_{n} \rangle$ and $\langle v'_{1}, \dots, v'_{n} \rangle$ on $V$ are *neighborhood-equivalent* if $N(v_{i}) = N(v'_{i})$ for all $i$.

\[[@HeggernesHMV15]\] \[lem:uniquerep\] Let $G$ be a connected bipartite permutation graph defined by $\prec_{1}$ and $\prec_{2}$. Then, every permutation ordering of $G$ is neighborhood-equivalent to $\prec_{1}$, $\prec_{2}$, $\prec_{1}^{\mathrm{R}}$, or $\prec_{2}^{\mathrm{R}}$.

A bipartite graph $(X,Y;E)$ is a *unit interval bigraph* if there is a set of unit intervals $\{I_{v} = [l_{v}, l_{v}+1] \mid v \in X \cup Y\}$ such that $xy \in E$ if and only if $I_{x} \cap I_{y} \ne \emptyset$ for $x \in X$ and $y \in Y$. The class of unit interval bigraphs is known to be equal to the class of bipartite permutation graphs.

\[[@SenS94; @West98; @HellH04]\] \[prop:bpg=uib\] 