Suppose you are given an undirected graph G.
Define a *layout* of G to be a way of
assigning distinct real-number coordinates to the vertices of G,
so that the edges of G can be represented as (open) intervals of the real
number line. Define the *bandwidth* of a layout
to be the maximum number of such intervals covering any point of the real
line. For instance, if G has vertices with coordinates 1,2,3,4, and
edges (1,3) (2,3) (3,4) and (1,4), then the bandwidth of this layout is
three, since three of the intervals cover the value 2.5.

The bandwidth of G itself is defined to be the minimum bandwidth of any
layout of G. For instance, the layout above is not the best possible: the
same graph has a layout with bandwidth two, so the bandwidth of G in this
example is two. Two layouts are equivalent (and have the same bandwidth)
if they form the same permutation of the vertices,
so one can compute the bandwidth of G by generate and test in time O(n!).

The homework problem is to devise a more efficient dynamic programming
algorithm for computing the bandwidth of a given graph.

Hint:
if you choose to permute the vertices so that some subset S is placed
with smaller coordinates than everything not in S, then what is the
optimal layout of S, and what can you say about the overall bandwidth of
the layout?

### Due by email
Monday, Nov. 13, 11:59PM.

Please **do not send MS Word** or other proprietary formats.
Plain text, TeX, HTML, or PDF are all acceptable.