We are investigating several problems in the layout of very large-scale integrated (VLSI) circuitry. We are interested in both placement (of modules) and routing (of their connecting wires). Recently, our investigations have focused on new techniques for routing made possible by emerging technology. Significant results have been obtained for multilayer routing and problems where layouts may be improved by allowing movable terminals. A new model of routing involving a hexagonal grid, instead of the traditional square grid, has proven to reduce the area requirements for a large class of problems. Also, new bounds on the area required for multilayer Manhattan routing are being developed.

For present-day computer science and technology, it is necessary to develop good algorithms and to compare their performance with the theoretically best possible performance on a selected computation model, or, equivalently, on a selected computing system. This is the subject of computational complexity studies that aim at a quantitative formulation of the inherent difficulty of problems. We designed a program checker for linked data structures. We developed parallel algorithms for computing the convex hull of a three-dimensional point set. We devised parallel and sequential algorithms for computing the minimum boundary-to-boundary distance between two simple polygons.