Finding the minimum bandwidth of an interval graph (Q1090458)

An assignment of unique integers to the vertices of a graph is called a linear layout. The bandwidth minimization problem (BANDWIDTH) is the following: Given a graph \(G=(V,E)\) and an integer k, determine whether there exists a linear layout of G such that the maximum difference between adjacent vertices is bounded by k. Interval graphs are the intersection graphs of a family of intervals of the real line. BANDWIDTH remains NP-complete even when restricted to special subclasses of trees. We show that BANDWIDTH can be solved in time \(O(n^ 2)\) for interval graphs. Moreover, for a given interval graph a linear layout with minimum bandwidth can be constructed in time \(O(n^ 2\log n)\). As a by-product we get that this construction can be done for proper interval graphs in time O(n log n\(+m)\).