## 3 Polynomial Time Algorithms for the Bandwidth Problem
### Linear Time Algorithm for a Chain Graph
We introduce a \(\mathsf{wiper}(x_{i})\) which is a line segment joining two points \(p_{1}\) and \(p_{2}\) on \(L_{1}\) and \(L_{2}\), respectively, on the line representation of a chain graph \(G=(X,Y,E)\) as follows (Figure 3(b)); \(p_{1}\) is a fixed point on \(L_{1}\) between \(x_{1}\) and \(y_{n^{\prime}}\), and \(p_{2}\) is a point on \(L_{2}\) between \(x_{i+1}\) and \(q\), where \(q\) is the right neighbor point of \(x_{i+1}\) on \(L_{2}\). More precisely, \(q\) is either (1) \(x_{i}\) if \(N(x_{i})=N(x_{i+1})\), or (2) the maximum vertex \(y_{j}\) in \(N(x_{i})\setminus N(x_{i+1})\) if \(N(x_{i})\setminus N(x_{i+1})\
eq\emptyset\). Using the wiper, \(H_{i}\) can be obtained from \(G\) by making a clique \(C_{i}\) which consists of the vertices corresponding to line segments intersecting \(\mathsf{wiper}(x_{i})\) on the line representation. Intuitively, the interval representation of \(H_{i}\) can be obtained as follows; first, we construct a line representation of \(G\) and put the \(\mathsf{wiper}(x_{i})\) (Figure 3(b)), second, we modify it to the intersection model of horizontal and vertical line segments with \(\mathsf{wiper}(x_{i})\) placed between \(x_{i}\) and \(x_{i+1}\) or \(y_{j}\), where \(y_{j}\) is the minimum vertex in \(N(x_{i+1})\) (Figure 3(c)), and finally, we stretch the \(\mathsf{wiper}(x_{i})\) to vertical line segment, or just a point 0 on an interval representation, and arrange the line segments corresponding to the vertices in \(X\) and \(Y\) (Figure 3(d)). We note that the interval representation of \(H_{i}\) in Figure 3(d) is a combination of two interval representations (Figure 1(b)) of two threshold graphs that are separated by the \(\mathsf{wiper}(x_{i})\). More precise and formal construction of the interval representation of \(H_{i}\) is as follows. By [PERSON]'s property, the intervals in the clique \(C_{i}\) share a common point, say 0 (which corresponds to \(\mathsf{wiper}(x_{i})\)). Then, centering the point 0, we can construct a symmetric interval representation as follows (Figure 3(d)); (1) each \(x_{i^{\prime}}\in X\) with \(i^{\prime}\leq i\) corresponds to an interval \([0,(d(x_{i^{\prime}})-d(x_{i}))]\), (2) each \(x_{i^{\prime}}\in X\) with \(i^{\prime}>i\) corresponds to the point \(-(i^{\prime}-i)=i-i^{\prime}(<0)\), (3) each \(y_{j}\in Y\) with \(j>n^{\prime}-d(x_{i+1})\) corresponds to an interval \([-(d(y_{j})-i),0]=[(ialgorithm in Section 3.1. (In Figure 3(d), \(H_{i}[X_{i}^{R}\cup Y_{i}^{R}]\) is induced by \(\{x_{1},x_{2},y_{1},y_{2}\}\) and \(H_{i}[X_{i}^{L}\cup Y_{i}^{L}]\) is induced by \(\{x_{3},x_{4},x_{5},x_{6},y_{3},y_{4},y_{5},y_{6}\}\).) Now we are ready to prove the main theorem in this section. **Theorem 9**: _We assume that a chain graph \(G=(X,Y,E)\) is given in \(O(n+n^{\prime})\) space as stated above. Then we can compute \(\mathsf{bw}(G)\) in \(O(n+n^{\prime})\) time and space._  
Proof. By Lemma 8, we can compute \(\mathsf{bw}(G)\) by computing the minimum \(\mathsf{bw}(H_{i})\) for \(i=0,1,2,\ldots,n-1\). By the fact that \(H_{0}\) is a threshold graph and Theorem 6, we can compute \(\mathsf{bw}(H_{0})\) in linear time and space. We only consider the case that \(1\leq i\leq n-1\). We separate the proof into three phases. Algorithm:Consider a fixed index \(i\). The basic idea is similar to the algorithm for a threshold graph. We directly construct a minimum completion of \(H_{i}\). When \(G\) is a threshold graph, we put a midpoint \(m\) such that each point \([j,j]\) less than or equal to \(m\) is extended to an interval \(I_{v}\) with \(R[I_{v}]=j\), and each point \([j,j]\) greater than \(m\) is extended to an interval \(I_{v}\) with \(L[I_{v}]=j\), where \(v\) is the vertex corresponding to the point \([j,j]\). Similarly, we put two midpoints \(\ell\) in \(H_{i}[X_{i}^{L}\cup Y_{i}^{L}]\) and \(r\) in \(H_{i}[X_{i}^{R}\cup Y_{i}^{R}]\). Now we make a proper interval representation instead of a unit interval representation to simplify the proof.