New lower bound techniques for VLSI

Abstract

In this paper, we use crossing number and wire area arguments to find lower bounds on the layout area and maximum edge length of a variety of computationally useful networks. In particular, we describe 1) an N-node planar graph which has layout area Θ(NlogN), and maximum edge length Θ(N1/2/log1/2N), 2) an N-node graph with an O(N1/2)-separator which has layout area Θ(Nlog2N) and maximum edge length Θ(N1/2logN/loglogN), and 3) an N-node graph with an O(N1-1/r)-separator which has maximum edge length Θ(N1-1/r) for any r ≥ 3.