@techreport{MPI-I-93-144,
TITLE = {A lower bound for area-universal graphs},
AUTHOR = {Bilardi, G. and Chaudhuri, Shiva and Dubhashi, Devdatt P. and Mehlhorn, Kurt},
LANGUAGE = {eng},
NUMBER = {MPI-I-93-144},
INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
ADDRESS = {Saarbr{\"u}cken},
YEAR = {1993},
DATE = {1993},
ABSTRACT = {We establish a lower bound on the efficiency of area--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 \leq \sqrt{A}/\log\log A$ satisfies the tradeoff $$ A_u = \Omega ( A \log A / (c^2 \log (2d)) ). $$ In particular, if $A_u = O(A)$ then $\max(c,d) = \Omega(\sqrt{\log A} / \log\log A)$.},
TYPE = {Research Report},
}