Abstract
In this paper we propose two new multilayer grid models for VLSI layout, both of which take into account the number of contact cuts used. For the first model in which nodes "exist" only on one layer, we prove a tight area × (number of contact cuts) = Θ(n2) tradeoff for embedding n-node planar graphs of bounded degree in two layers. For the second model in which nodes "exist" simultaneously on all layers, we give a number of upper bounds on the area needed to embed groups using no contact cuts. We show that any n-node graph of thickness 2 can be embedded on two layers in O(n2) area. This bound is tight even if more layers and any number of contact cuts are allowed. We also show that planar graphs of bounded degree can be embedded on two layers in O(n3/2(log n)2) area. Some of our embedding algorithms have the additional property that they can respect prespecified grid placements of the nodes of the graph to be embedded. We give an algorithm for embedding n-node graphs of thickness k in k layers using O(n3) area, using no contact cuts, and respecting prespecified node placements. This area is asymptotically optimal for placement-respecting algorithms, even if more layers are allowed, as long as a fixed fraction of the edges do not use contact cuts. Our results use a new result on embedding graphs in a single-layer grid, namely an embedding of n-node planar graphs such that each edge makes at most four turns, and all nodes are embedded on the same line. © 1991 Springer-Verlag New York Inc.