@techreport{Report-223-1989,
Title = {Graph Problems related to Gate Matrix Layout and PLA Folding},
Author = {Rolf H. M\"ohring},
Booktitle = {Computational Graph Theory, 1990},
Pages = {17-52},
Year = {1989},
Number = {223},
Editor = {G. Tinhofer et al.},
Publisher = {Springer-Verlag} # { Wien},
Type = {Preprint},
Institution = {Technische Universit\"at Berlin, Institut f\"ur Mathematik},
Abstract = {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.}
}