## 2 Preliminaries
Moreover, each connected proper interval graph has essentially unique proper (or unit) interval representation up to reversal in the following sense (see, e.g., [45, Corollary 2.5]):  
**Proposition 1**: _For any connected proper interval graph \(G=(V,E)\) without twins, there is a unique ordering (up to reversal) \(v_{1},v_{2},\ldots,v_{n}\) of \(n\) vertices such that \(G\) has a unique proper interval representation \(\mathcal{I}(G)\) such that \(L(I_{v_{1}})<L(I_{v_{2}})<\cdots<L(I_{v_{n}})\) (and hence \(R(I_{v_{1}})<R(I_{v_{2}})<\cdots<R(I_{v_{n}})\)). In other words, for a connected proper interval graph \(G=(V,E)\) without twins, there exists a vertex ordering \(v_{1},v_{2},\ldots,v_{n}\) such that every interval representation of \(G\) satisfies either \(L(I_{v_{1}})<L(I_{v_{2}})<\cdots<L(I_{v_{n}})\) or \(L(I_{v_{n}})<\cdots<L(I_{v_{2}})<L(I_{v_{1}})\)._  
We note that when \(G\) contains twins \(u\) and \(v\), they correspond to the congruent intervals with \(L(I_{v})=L(I_{u})\) and \(R(I_{v})=R(I_{u})\). In a sense, the ordering is still unique even if \(G\) contains twins up to isomorphism if the graph is unlabeled. For any interval representation \(\mathcal{I}\) and a point \(p\), \(N[p]\) denotes the set of intervals that contain the point \(p\). A graph \(G=(V,E)\) is called a _threshold graph_ when there exist nonnegative weights \(w(v)\) for all \(v\in V\) and a threshold value \(t\) such that \(\{u,v\}\in E\) if and only if \(w(u)+w(v)\geq t\). Let \(G=(X,Y,E)\) be a bipartite graph with \(X=\{x_{1},x_{2},\,\ldots,\,x_{n}\}\) and \(Y=\{y_{1},y_{2},\,\ldots,\,y_{n^{\prime}}\}\). The ordering of \(X\) has the _adjacency property_ if and only if, for each vertex \(y\in Y\), \(N(y)\) consists of vertices that are consecutive in the ordering of \(X\). A bipartite graph \(G=(X,Y,E)\) is said to be a _chain graph_ if and only if there are orderings of \(X\) and \(Y\) that fulfill the adjacency property, and the ordering of \(X\) satisfies that \(N(x_{n})\subseteq N(x_{n-1})\subseteq\cdots\subseteq N(x_{1})\). (The last property implies that the ordering of \(Y\) also satisfy \(N(y_{1})\subseteq N(y_{2})\subseteq\cdots\subseteq N(y_{n^{\prime}})\); see, e.g., [46].) A graph \(G=(V,E)\) with \(V=\{v_{1},v_{2},\ldots,v_{n}\}\) is said to be a _permutation graph_ if and only if there is a permutation \(\sigma\) over \(V\) such that \(\{v_{i},v_{j}\}\in E\) if and only if \((i-j)(\sigma(v_{i})-\sigma(v_{j}))<0\). Intuitively, each vertex \(v\) in a permutation graph corresponds to a line segment \(\ell_{v}\) joining two points on two parallel line segments \(L_{1}\) and \(L_{2}\). Then two vertices \(v\) and \(u\) are adjacent if and only if the corresponding line segments \(\ell_{v}\) and \(\ell_{u}\) intersect. The ordering of vertices gives the ordering of the points on \(L_{1}\), and the permutation of the ordering gives the ordering of the points on \(L_{2}\). We call the intersection model a _line representation_ of the permutation graph. When a permutation graph is bipartite, it is said to be a _bipartite permutation graph_. Although a permutation graph has (exponentially)many line representations, a connected bipartite graph essentially has a unique line representation up to isomorphism (see [47, Lemma 3] for further details):  
**Lemma 2**: _Let \(G=(V,E)\) be a connected bipartite permutation graph without twins. Then the line representation of \(G\) is unique up to isomorphism._  
The following proper inclusions are known (see, e.g., [46, 48]):  
**Lemma 3**: _(1) Threshold graphs \(\subset\) interval graphs; (2) chain graphs \(\subset\) bipartite permutation graphs._  
A natural bipartite analogy of interval graphs are called _interval bigraphs_ which are intersection graphs of two-colored intervals so that we do not join two vertices if they have the same color. Based on the definition, [PERSON] showed that the recognition problem for interval bigraphs can be solved in polynomial time [49].