Bandwidth of convex bipartite graphs and related graphs

We show that the bandwidth problem is NP-complete for convex bipartite graphs. We provide an O(n)-time, 4-approximation algorithm and an -time, 2-approximation algorithm to compute the bandwidth of convex bipartite graphs with n vertices. We also consider 2-directional orthogonal ray graphs, a superclass of convex bipartite graphs, for which we provide an -time, 3-approximation algorithm, where n is the number of vertices.