We develop a simple linear time algorithm to determine if a collection of two-pin nets can be routed, topologically, in a plane (i.e., single layer). Experiments indicate that this algorithm is faster than the linear time algorithm of Marek-Sadowska and Tarng. Topological routability testing of a collection of multipin nets is shown to be equivalent to planarity testing, and a simple linear time algorithm is developed for the case when the collection of modules remains connected following the deletion of all nets with more than two pins.

We study the problem of folding an ordered list of standard and custom cells into rows of a chip so as to minimize either the routing area or the total chip area. Nine versions of the folding problem are formulated and fast polynomial time algorithms are obtained for each. Two of our formulations correspond to problems formulated in Paik and Sahni [1993] for the folding of a stack of bit-slice components. Our algorithms for these two formulations are asymptotically superior to those of Paik and Sahni [1993].

We consider two versions of the problem of folding a stack of equal width components. In both versions, when a stack is folded, a routing penalty is incurred at the fold. In one version, the height of the folded layout is given and we are to minimize width. In the other, the width of the folded layout is given and its height is to be minimized. We develop a normalization technique that permits the first version to be solved in linear time by a greedy algorithm. The second version can be solved efficiently using normalization and parametric search. Experimental results are presented.>