The principal investigator is addressing graph embedding issues arising in layout of VLSI designs and mapping of parallel algorithms to parallel computing structures. With respect to layout, Dr. Hambrusch is investigating problems motivated by multilayer models, including problems of linear arrangement and partitioning nonplanar problems into planar ones. Cost measures used are individual and total wire length, and number of layers. With respect to parallel processing, the problem is the embedding of a source interconnection network into a host network of smaller size. Concentration is on tree and mesh-like networks and the algorithmic behavior of the source network. Such embeddings will be tailored towards the parallel functions and subroutines used in the algorithm for the source network.
