Two-Layer Channel Routing with Vertical Unit-Length Overlap

We show that any n-net 2-terminal channel routing problem of density d can be wired on a two-layer grid of width w = d + 0 (d1J3) when vertical wire segments are allowed to overlap for a dis-tance of length 1. TItis is a considerable asymptotic improvement over the best known, and optimal, channel width of 2d-l for models in which no vertical overlap is allowed [RBM, PL]. OUf result also improves the 3d12 + 0(1) channel width achieved by a recent algorilhm [0] for the same vertical overlap model. The algorithm presented in this paper produces at most 4 over-laps of unit length between any two nets, uses 0 (n) contacts, and can be implemented to run in O(nd2l3) time. We also generalize the algorithm to multi-terminal channel routing problems for which our algorithm uses a width ofw = 2d + 0 (d 2J3)