## 3 Polynomial Time Algorithms for the Bandwidth Problem
### Linear Time Algorithm for a Chain Graph  
We next show a linear time algorithm for computing \(\mathsf{bw}(G)\) of a connected chain graph \(G=(X,Y,E)\). We assume that \(X=\{x_{1},x_{2},\ldots,x_{n}\}\) and \(Y=\{y_{1},y_{2},\ldots,y_{n^{\prime}}\}\) are already ordered by inclusion of neighbors; \(N(x_{n})\subseteq N(x_{n-1})\subseteq\cdots\subseteq N(x_{1})\) and \(N(y_{1})\subseteq N(y_{2})\subseteq\cdots\subseteq N(y_{n^{\prime}})\). Since \(G\) is connected, we have \(N(x_{1})=Y\) and \(N(y_{n^{\prime}})=X\). We assume that a chain graph \(G=(X,Y,E)\) with \(|X|=n\) and \(|Y|=n^{\prime}\) is given in \(O(n+n^{\prime})\) space; each vertex \(y\in Y\) stores one endpoint \(d(y)\) such that \(N(y)=\{x_{1},x_{2},\ldots,x_{d(y)}\}\), and each vertex \(x\in X\) stores one endpoint \(n^{\prime}-d(x)+1\) such that \(N(x)=\{y_{n^{\prime}},y_{n^{\prime}-1},\ldots,y_{n^{\prime}-d(x)+1}\}\). (We abuse the degree \(d(\cdot)\) as a maximum index of the neighbors.) A chain graph has an intersection model of horizontal and vertical line segments (an example in Figure 3(a) has an intersection model in Figure 3(c)); \(X\) corresponds to a set of horizontal line segments such that all left endpoints have the same \(x\)-coordinate, and \(Y\) corresponds to a set of vertical line segments such that all top endpoints have the same \(y\)-coordinate. By the property of the inclusions of neighbors, on the intersection model, vertices in \(X\) can be placed from top to bottom and vertices in \(Y\) can be placed from right to left such that the lengths of their line segments are monotone. This also can be transformed to the line representation of a bipartite permutation graph in a natural way (Figure 3(b)). Then the endpoints on \(L_{1}\) are sorted as \(x_{n},\ldots,x_{1},y_{n^{\prime}},\ldots,y_{1}\) from left to right. Figure 3: Chain graph (**a**) and its corresponding representations (**b**)–(**e**). For a chain graph \(G=(X,Y,E)\), a graph \(H_{i}=(X\cup Y,E_{i})\) is defined as follows [24]: We first define \(H_{0}=(X\cup Y,E_{0})\) to be a graph obtained from \(G\) by making a clique of \(X\); that is, \(E_{0}=E\cup\{\{x,x^{\prime}\}\mid x,x^{\prime}\in X\text{ and }x\
eq x^{\prime}\}\). For \(1\leq i\leq n-1\), let \(C_{i}\) be the set \(\{x_{1},x_{2},\ldots,x_{i}\}\cup N(x_{i+1})\). Then the graph \(H_{i}\) is obtained from \(G\) by making a clique of \(C_{i}\). More precisely, \(E_{i}:=E\cup\{\{x_{i^{\prime}},x_{i^{\prime\prime}}\}\mid 1\leq i^{\prime},i^{ \prime\prime}\leq i\}\cup\{\{y_{j^{\prime}},y_{j^{\prime\prime}}\}\mid(n^{ \prime}-d(x_{i+1})+1)\leq j^{\prime},j^{\prime\prime}\leq n^{\prime}\}\). Then, the following lemma plays an important role in the algorithm in [24], which computes the \(\mathsf{bw}(G)\) for a chain graph \(G\) by finding the minimum value of \(\mathsf{bw}(H_{i})\) for each \(i\). **Lemma 8** ([24]): _(1) \(H_{i}\) is an interval graph for each \(i\); (2) \(\mathsf{bw}(G)=\min_{i}\mathsf{bw}(H_{i})\)._  
We first observe that \(H_{0}\) is a threshold graph that has an interval representation in the form shown in Figure 3(c); that is, we project the representation in Figure 3(c) onto a horizontal line. The length of each \(x_{i}\) does not change, and each \(y_{j}\) degenerates to a point on the line. Intuitively, we can regard each \(y\in Y\) as a point and each \(x\in X\) as an interval. More precisely, we assign the weights of the vertices as follows. For each \(y_{j}\in Y\), \(w(y_{j})=j\). For each \(x_{i}\in X\), \(w(x_{i})=2|X|+|Y|-j\), where \(j\) is the minimum index of \(N(x)\). Letting \(t=2|X|+|Y|\), we can obtain the desired threshold graph with interval representation obtained from the projection of one in Figure 3(c). Thus, by Theorem 6, \(\mathsf{bw}(H_{0})\) can be computed in \(O(n+n^{\prime})\) time and space. Hereafter, we construct all minimum completions of \(H_{i}\) directly for \(1\leq i\leq n-1\).