A LOWER-BOUND FOR AREA-UNIVERSAL GRAPHS

Authors
BILARDI G CHAUDHURI S DUBHASHI D MEHLHORN K
Citation
G. Bilardi et al., A LOWER-BOUND FOR AREA-UNIVERSAL GRAPHS, Information processing letters, 51(2), 1994, pp. 101-105
Citations number
5
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
51
Issue
2
Year of publication
1994
Pages
101 - 105
Database
ISI
SICI code
0020-0190(1994)51:2<101:ALFAG>2.0.ZU;2-B
Abstract
We establish a lower bound on the efficiency of area-universal circuit s. The area A(u) of every graph H that can host any graph G of area (a t most) A with dilation d, and congestion c less-than-or-equal-to squa re-root A/log log A satisfies the tradeoff A(u) = OMEGA(A log A/(c2 lo g(2d))). In particular, if A(u) = O(A) then max(c, d) = OMEGA(square-r oot log A/log log A).