## 3 Polynomial Time Algorithms for the Bandwidth Problem
### Linear Time Algorithm for a Chain Graph
(We note that any proper interval representation can be extended to a unit interval representation in a natural way [44]. Hence we can use a proper interval representation instead of a unit interval representation.) For two midpoints \(\ell\) and \(r\), we make a proper interval representation as follows; (1) for each \(x_{i^{\prime}}\in X_{i}^{L}\) with \(i^{\prime}\geq\ell\), \(I^{\prime}_{x_{i^{\prime}}}=[i-n..i-i^{\prime}]\), (2) for each \(x_{i^{\prime}}\in X_{i}^{L}\) with \(\ell<i^{\prime}\), \(I^{\prime}_{x_{i^{\prime}}}=[i-i^{\prime}..0]\), (3) for each \(y_{j}\in Y_{i}^{R}\) with \(r<j(\leq n^{\prime}-d(x_{i+1}))\), \(I^{\prime}_{y_{j}}=[0..i-j+1]\), and (4) for each \(y_{j}\in Y_{i}^{R}\) with \(j\leq r\), \(I^{\prime}_{y_{j}}=[i-j+1..i]\). In Figure 3(e), we give an example with \(\ell=5\) and \(r=1\). For each possible pair \((\ell,r)\) of \(\ell\) and \(r\) with \(i+2\leq\ell\leq n\) and \(1\leq r\leq n^{\prime}-d(x_{i+1})-1\), we compute the size of a maximum clique in the proper interval representation. At this time, we have three candidates for a maximum clique at the left, the center, and the right parts of the proper interval representation. More precisely, for each fixed \(i\), \(\ell\), and \(r\), we define three maximum cliques \(\mathsf{RC}_{i}(\ell,r)\), \(\mathsf{CC}_{i}(\ell,r)\), and \(\mathsf{LC}_{i}(\ell,r)\) in three proper interval graphs induced by \(\{x_{\ell},x_{\ell+1},\ldots,x_{n}\}\cup\{y_{j},y_{j+1},\ldots,y_{n^{\prime}}\}\), where \(y_{j}\) is the minimum vertex in \(N(x_{\ell})\), \(\{x_{1},x_{2},\ldots,x_{\ell-1}\}\cup\{y_{r+1},y_{r+2},\ldots,y_{n^{\prime}}\}\), and \(\{x_{1},x_{2},\ldots,x_{i^{\prime}}\}\cup\{y_{1},y_{2},\ldots,y_{r}\}\), where \(x_{i^{\prime}}\) is the maximum vertex in \(N(y_{r})\), respectively. For example, in Figure 3(e), three sets are \(\{x_{5},x_{6},y_{4},y_{5},y_{6}\}\), \(\{x_{1},x_{2},x_{3},x_{4},y_{2},y_{3},y_{4},y_{5},y_{6}\}\), and \(\{x_{1},x_{2},y_{1}\}\), and hence \(\mathsf{RC}_{i}(5,1)=\{x_{5},y_{4},y_{5},y_{6}\}\) at point -3 (or \(R(x_{5})\)), \(\mathsf{CC}_{i}(5,1)=\{x_{1},x_{2},x_{3},x_{4},y_{2},y_{3},y_{4},y_{5},y_{6}\}\) at point 0, and \(\mathsf{LC}_{i}(5,1)=\{x_{1},x_{2},y_{1}\}\) at point 2. Thus for \((\ell,r)=(5,1)\), we have a maximum clique \(\mathsf{CC}_{i}(5,1)\) of size \(9\). For each pair \((\ell,r)\), we compute \(\max\{|\mathsf{RC}_{i}(\ell,r)|,|\mathsf{CC}_{i}(\ell,r)|,|\mathsf{LC}_{i}( \ell,r)|\}\), and then we take the minimum value of \(\max\{|\mathsf{RC}_{i}(\ell,r)|,|\mathsf{CC}_{i}(\ell,r)|,|\mathsf{LC}_{i}( \ell,r)|\}\) for all pairs, which is equal to \(\mathsf{bw}(H_{i})+1\) for the fixed \(i\). In the case in Figure 3(d) (\(i=2\)), \((\ell,r)=(3,2)\) gives the minimum value \(6(=\mathsf{RC}_{2}(3,2)=\mathsf{CC}_{2}(3,2))\). We next compute the minimum one for all \(i\), which gives \(\mathsf{bw}(G)+1\). Summarizing, we have Algorithm 3. Correctness:By Lemma 8, each graph \(H_{i}\) is an interval graph and \(\min_{i}\mathsf{bw}(H_{i})=\mathsf{bw}(G)\). For the interval representation of \(H_{i}\), we consider two proper interval subgraphs. The first induced subgraph \(H_{i}[X_{i}^{R}\cup Y_{i}^{L}]\), which consists of positive length intervals in \(H_{i}\), is a proper interval graph, and the second induced subgraph \(H_{i}[X_{i}^{L}\cup Y_{i}^{R}]\), which consists of intervals of length 0 (or points), is also a proper interval graph. Hence, by Lemma 5, there is an optimal layout that keeps their natural orderings over \(X_{i}^{R}\cup Y_{i}^{L}\) and \(X_{i}^{L}\cup Y_{i}^{R}\). Therefore, by Observation 4, we can compute \(\mathsf{bw}(H_{i})\) by extending intervals in them together to be proper. Using the same argument as in the proof of Theorem 6, we can use the set \(X_{i}^{R}\cup Y_{i}^{L}\) of intervals as a proper interval representation as is, and we must extend each interval in \(X_{i}^{L}\cup Y_{i}^{R}\) to be proper with respect to \(X_{i}^{R}\cup Y_{i}^{L}\). Using the same argument twice, we can see that using the idea of two midpoints \(\ell\) and \(r\) achieves an optimal layout.