Layering Algorithms For Single-Row Routing

Abstract

We develop two fast algorithms for the layering problem that arises when the single-row routing approach to wire layout is used. Both of these algorithms are for the case when the upper and lower street capacities are two. While neither of these algorithms guarantees the production of an optimal layering, it has been empirically determined that both will produce better layerings than an earlier proposed algorithm [13] for this problem. In addition, our algorithms run much faster than the earlier algorithm.