A new lower bound for channel routing

Channel routing is a key problem in the physical design of VLSI chips. It is known that max(d/sub max/, /spl upsi//sub max/) is a lower bound on the number of tracks required in the reserved two-layer Manhattan routing model, where d/sub max/ is the channel density and v/sub max/ is the length of the longest path in the vertical constraint graph. We propose a polynomial time algorithm that computes a better lower bound on the number of tracks required for routing. This algorithm is also applicable for computing a lower bound on the number of tracks in the three-layer HVH routing model.<>