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(N^1/2), (ii) a layout with area O(N^5/4) and maximum edge length O(N^1/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.