## 3 Polynomial Time Algorithms for the Bandwidth Problem  
A _layout_ of a graph \(G=(V,E)\) on \(n\) vertices is a bijection \(\pi\) between the vertices in \(V\) and the set \(\{1,2,\ldots,n\}\). The _bandwidth of a layout_\(\pi\) equals \(\max\{|\pi(u)-\pi(v)|\mid\{u,v\}\in E\}\). The _bandwidth of \(G\)_, denoted by \(\text{bw}(G)\), is the minimum bandwidth of all layouts of \(G\). A layout achieving \(\text{bw}(G)\) is called an _optimal layout_. On a layout \(\pi\), we denote by \(S<S^{\prime}\) for two vertex sets \(S,S^{\prime}\) if and only if \(\pi(u)<\pi(v)\) holds for every pair of \(u\in S\) and \(v\in S^{\prime}\). For given graph \(G=(V,E)\), a _proper interval completion of \(G\)_ is a superset \(E^{\prime}\) of \(E\) such that \(G^{\prime}=(V,E^{\prime})\) is a proper interval graph. Hereafter, we will omit the \"proper interval\" since we always consider proper interval completions. We say a completion \(E^{\prime}\) is _minimum_ if and only if \(|C^{\prime}|\leq|C^{\prime\prime}|\) for maximum cliques \(C^{\prime}\) in \(G^{\prime}=(V,E^{\prime})\) and \(C^{\prime\prime}\) in \(G^{\prime\prime}=(V,E^{\prime\prime})\) for any other completion \(E^{\prime\prime}\). For a minimum completion \(E^{\prime}\), it is known that \(\text{bw}(G)=|C^{\prime}|-1\), where \(C^{\prime}\) is a maximum clique in \(G^{\prime}=(V,E^{\prime})\)[9]. Let \(G=(V,E)\) be an interval graph with an interval representation \(\mathcal{I}=\{I_{v_{1}},I_{v_{2}},\ldots,I_{v_{n}}\}\). For each maximal clique \(C\), there is a point \(p\) such that \(N[p]\) induces the clique \(C\) by Helly property. Thus, for any given graph \(G\), we can compute \(\text{bw}(G)\) by Algorithm 1. ```
Input : Graph \(G=(V,E)\) Output : \(\text{bw}(G)\)  generate a proper interval graph \(G^{\prime}=(V,E^{\prime})\) that gives a minimum completion of \(G\);  make the unique proper interval representation \(\mathcal{I}(G^{\prime})\) of \(G^{\prime}\);  find a point \(p\) such that \(|N[p]|\geq|N[p^{\prime}]|\) for any other point \(p^{\prime}\) on \(\mathcal{I}(G^{\prime})\); return\((|N[p]|-1)\). ```  
**Algorithm 1**Bandwidth of a general graph  
In Algorithm 1, the key point is how to find the minimum completion of \(G\) in the first step. The following observation may not be explicitly given in literature, but it can be obtained from the results in [9] straightforwardly (for example, the proof of Theorem 3.2 in [9], this fact is implicitly used):  
**Observation 4**: _For a minimum completion \(G^{\prime}=(V,E^{\prime})\) of \(G=(V,E)\), let \(\mathcal{I}(G^{\prime})=(I^{\prime}_{v_{1}},I^{\prime}_{v_{2}},\ldots,I^{ \prime}_{v_{n}})\) be the unique proper interval representation of \(G^{\prime}\) stated in Proposition 1. Then the ordering \(v_{1},v_{2},\ldots,v_{n}\) gives an optimal layout of \(G\), and vice versa._  
Here we show a technical lemma for the proper interval subgraph of an interval graph that will play an important role of our results. **Lemma 5**: _Let \(G=(V,E)\) be an interval graph with \(V=\{v_{1},v_{2},\ldots,v_{n}\}\), and \(\mathcal{I}=\{I_{v_{1}},I_{v_{2}},\ldots,I_{v_{n}}\}\) an interval representation of \(G\). Let \(\mathcal{J}=\{J_{u_{1}},J_{u_{2}},\ldots,J_{u_{k}}\}\) be a subset of \(\mathcal{I}\) such that \(\mathcal{J}\) forms a proper interval representation. That is, we have \(U=\{u_{1},\ldots,u_{k}\}\subseteq V\), and we can order \(\mathcal{J}\) as \(L(J_{u_{i}})\leq L(J_{u_{i+1}})\) and \(R(J_{u_{i}})\leq R(J_{u_{i+1}})\) for each \(1\leq i<k\). Let \(\rho\) be the injection from \(\mathcal{J}\) to \(\mathcal{I}\) with \(J_{u_{i}}=I_{v_{\rho(i)}}\) for each \(1\leq i\leq k\leq n\). Then, \(G\) has an optimal layout \(\pi\) such that each interval \(J_{u_{i}}\) appears according to the ordering in \(\mathcal{J}\). More precisely, for each \(i\) with \(1\leq i<k\), we have \(\pi(v_{\rho(i)})<\pi(v_{\rho(i+1)})\)._  
Proof. The proof is strongly related to the algorithm, which we call Algorithm KV, developed by [PERSON] and [PERSON] in [26]. To be self-contained, we give a description of Algorithm KV in Appendix A.