As I mentioned, it's graph bandwidth (see Garey and Johnson).  Here
are more refs than you would ever want!  The Knuth paper is fun --
it's the most complicated algorithm I've ever seen (I think there are
64 different subcases).

@article{Papadimitriou:NP-complete,
	author = {Christos Papadimitriou},
	title = {The {NP}-completeness of the Bandwidth Minimization Problem},
	journal = {Computing},
	volume = 16,
	pages = {263--270},
	year = 1976}
@article{Garey:bandwidth,
	author = {Michael Garey and Ronald Graham and David Johnson and
	          Donald Knuth},
	title = {Complexity Results for Bandwidth Minimization},
	journal = SIAMJAM,
	volume = 34,
	pages = {477--495},
	year = 1978}
@incollection{Cuthill:strategies,
	author = {Elizabeth Cuthill},	
	title = {Several Strategies for Reducing the Bandwidth of Matrices},
	booktitle = {Sparse Matrices and Their Applications},
	editor = {D. J. Rose and R. A. Willoughby},
	publisher = {Plenum Press, New York},
	year = 1972}
@article{Gibbs:algorithm,
	author = {Norman Gibbs and William Poole and Paul Stockmeyer},
	title = {An Algorithm for Reducing the Bandwidth and Profile of a 
	Sparse Matrix},
	journal = {{SIAM} Journal of Numerical Analysis},
	volume = 13,
	number = 2,
	month = {April},
	year = 1976}
@Article{Chinn:survey,
  author = 	"P. Z. Zinn and J. Chv\'atalov\'a and A. K. Dewdney
		 and N. E. Gibbs",
  title = 	"The Bandwidth Problem for Graphs and Matrices --- A Survey",
  journal = 	"Journal of Graph Theory",
  year = 	"1982",
  volume = 	"6",
  number = 	"3",
  pages = 	"223--254"
}
@Article{Saxe:dynamic,
  author = 	"James Saxe",
  title = 	"Dynamic Programming Algorithms for Recognizing Small
		 Bandwidth Graphs in Polynomial Time",
  journal = 	SIAMJADM,
  year = 	"1980",
  volume = 	"1",
  number = 	"4",
  pages = 	"363--369",
  month = 	dec
}
@Article{Gurari:improved,
  author = 	"Eitan Gurari and Ivan Sudborough",
  title = 	"Improved Dynamic Programming Algorithms for Bandwidth
		 Minimization and the MinCut Linear Arrangement
		 Problem",
  journal = 	JALG,
  year = 	"1984",
  volume = 	"5",
  OPTnumber = 	"4",
  pages = 	"531--546",
  month = 	dec
}
@Article{Monien:TCS,
  author = 	"Burkhard Monien and Ivan Sudborough",
  title = 	"Bandwidth Constrained {NP}-Complete Problems",
  journal = 	TCS,
  year = 	"1985",
  volume = 	"41",
  pages = 	"141--167"
}