Understanding the bandwidth problem on graphs
I think you got the definition of bandwidth wrong. Here is your definition of the bandwidth of an ordering of the vertices:


  The bandwidth is the maximum distance in the graph between adjacent nodes in the ordering.


The correct definition is:


  The bandwidth is the maximum distance in the ordering between adjacent nodes in the graph.


Your problem is equivalent to the usual one – just take the inverse of the ordering permutation to get from one to the other.