An $O( n \log n )$ Algorithm for Bandwidth of Interval Graphs
Alan Sprague · SIAM Journal on Discrete Mathematics · 1994
This paper presents an $O( n\log n )$ algorithm for the bandwidth problem on interval graphs. Given an interval model for an interval graph with n vertices and an integer k, the algorithm constructs a layout of bandwidth at most k, if there exists one. Two previous algorithms for this problem have been published. One of them is flawed; the other is by Kleitman and Vohra and has complexity $O( nk )$.