This paper gives a survey on graph problems occuring
in linear VLSI layout architectures such as gate matrix
layout, folding programmable logic arrays, and
Weinberger arrays. These include a variety of mostly
independently investigated graph problems such as
augmentation of a given graph to an interval graph with
small clique size, node search of graphs, matching
problems with side constraints, and other. We discuss
implications of graph theoretic results for the VLSI
layout problems and survey new research directions. New
results presented include NP-hardness of gate
matrix-layout on chordal graphs, efficient algorithms
for trees, cographs, and certain chordal graphs,
Lagrange relaxation and approximation algorithms based
on on-line interval graph augmentation.
