## 1 Introduction
The bandwidth problem is \(\mathcal{NP}\)-complete not only for trees, but also for split graphs [14] and convex bipartite graphs [15]. From the viewpoint of exact algorithms, the problem seems to be a difficult one; [PERSON] developed an \(O(10^{n})\) time exact algorithm for the bandwidth problem of general graphs in 2000 [16], and recently, [PERSON] and [PERSON] improved it to \(O(4.383^{n})\) time (see [17, 18, 19] for further details). Therefore approximation algorithms for several graph classes have been developed (see, e.g., [15, 20, 21, 22, 23]). Only a few graph classes have been known for which the bandwidth problem can be solved in polynomial time. These include chain graphs [24], cographs and related classes (see [25] for the details), interval graphs [26, 27, 28], and bipartite permutation graphs [6, 29] (see [25] for a comprehensive survey). One of the interesting graph classes for which the bandwidth problem can be solved efficiently is the class of interval graphs. In 1987, [PERSON] proposed a polynomial time algorithm of the bandwidth problem for interval graphs [30]. Unfortunately, the algorithm has a flaw, which has been fixed by [PERSON] _et al._[27]. [PERSON] and [PERSON] also show a polynomial time algorithm [26], and [PERSON] the time complexity to \(O(n\log n)\) by sophisticated implementation of the algorithm [28]. All the algorithms above solve the decision problem that asks if an interval graph \(G\) has bandwidth at most \(k\) for given \(G\) and \(k\). Thus, using binary search for \(k\), we can compute the bandwidth \(\mathsf{bw}(G)\) of an interval graph \(G\) in \(O(M(n)\cdot\log\mathsf{bw}(G))\) time, where \(M(n)=O(n\log n)\) is the time complexity to solve the decision problem [28]. In the literature, it is mentioned that there are two unsolved problems for interval graphs. The first one is direct computation of the bandwidth of an interval graph. All the known algorithms are strongly dependent on the given upper bound \(k\) to construct a desired layout. To find a best layout directly, we need deeper insight into the problem and/or the graph class. The second one is to improve the time complexity to linear time. Since interval graphs have a relatively simple representation, many \(\mathcal{NP}\)-hard problems can be solved in linear time including early results of recognition [31] and graph isomorphism [32]. Another interesting class consists of chain graphs. Chain graphs form a compact subclass of bipartite permutation graphs that plays an important role in developing efficient algorithms for the class of bipartite permutation graphs [33, 34]. The algorithm by [PERSON], [PERSON], and [PERSON] computes the bandwidth of a chain graph in \(O(n^{2}\log n)\) time [24]. Their algorithm uses the algorithm for an interval graph as a subroutine, and the factor \(O(n\log n)\) comes from the time complexity to solve the bandwidth problem for the interval graph in [28]. In this paper, we propose simple algorithms for the bandwidth problem for the classes of threshold graphs and chain graphs. The first algorithm computes the bandwidth of a threshold graph \(G\) in \(O(n)\) time and space. We note that threshold graphs form a proper subclass of interval graphs, and can be represented in a compact representation of \(O(n)\) space. The algorithm directly constructs an optimal layout, that is, we give a partial answer to the open problem for interval graphs, and improve the previously known upper bound \(O(n\log n\log\mathsf{bw}(G))\) to optimal. Extending the first algorithm for threshold graphs, we next show an algorithm that computes the bandwidth of a chain graph in \(O(n)\) time and space. This algorithm also directly constructs an optimal layout, and improves the previously known bound \(O(n^{2}\log n)\) in [24] to optimal. More precisely, we first give a simple interval representation for a given threshold graph, and simplify the previously known algorithm for interval graphs. (We also show a new property of a previously known algorithm to show correctness.)