next up previous
Next: On the single-operation worst-case Up: Abstracts Previous: An lower bound on nth

An Area-Maximum Edge Length Trade-off for VLSI Layout

We construct an N-node graph G which has (i) a layout with area O(N) and maximum edge length O(N1/2), (ii) a layout with area O(N5/4) and maximum edge length O(N1/4). We prove for $1 \leq f(N) \leq O(N^{1/8})$ that any layout for G with area N f(N) has an edge of length $\Omega(N^{1/2}/f(n) \cdot \log N)$. Hence G has no layout which is optimal with respect to both measures.

Claus Rick