Item

Abstract

We establish a lower bound on the efficiency of rea--universal circuits. The area A u of every graph H that can host any graph G of area (at most) A with dilation d, and congestion c p A= log log A satisfies the tradeoff A u = OmegaGamma A log A=(c 2 log(2d))): In particular, if A u = O(A) then max(c; d) = OmegaGamma p log A= log log A). 1 Introduction Bay and Bilardi [2] showed that there is a graph H which can be laid out in area O(A) and into which any graph G of area at most A can be embedded with load 1, and dilation and congestion O(log A). As a consequence, they showed the existence of an area O(A) VLSI circuit that can simulate any area A circuit with a slowdown of O(log A). This note explores the feasibility of more efficient embeddings. Our main result is Theorem 5 which establishes a limitation relating the area of a universal graph to the parameters of the embedding. Informally, it asserts that any circuit which is universal for a family of graphs of area A, a...