Minimizing Contact Points and Using Overlap on Two Layers
Susanne E. Hambrusch · Purdue e-Pubs (Purdue University System) · 1983
We study solutions for 2-1ayer models that mlffimlze the number of contact points and the effect of overlap on the channel width. All known algorithms [or the 2-1ayer model without overlap usc 8(dn) contact points. We present an algorithm Cor a restricted class of channel routing problems that uses 2d -1 tracks and D(n) contact points. While channel rouling problems of this restricted class were successfully used to prove lower bounds on the channel width, any proof that 2d-l tracks and D(n) contact points cannot be achieved simultaneously in general in this model must make use or ;;;ome special properties not present in the restricted channel rouLing problem. We supply insight into those properties and into some of the dHIiculties that must be overcome by an algorithm that uses D(n) contact points. :lor the 2-layer model with overlap we present an algorithm that solves any channel rouUng problem on a chanr!cl of 2d-l tracks using at mosl 3n contact points and vertical overlap of length 1. We also present a lower bound on Lhe channel wldlh for the k -layer model with k -fold overlap, k=:=2.