A lower bound for area-universal graphs

Bilardi, G.; Chaudhuri, Shiva; Dubhashi, Devdatt P.; Mehlhorn, Kurt

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Report

A lower bound for area-universal graphs

MPS-Authors

Bilardi, G.
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons44233

Chaudhuri, Shiva
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons45021

Mehlhorn, Kurt
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource

No external resources are shared

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

Fulltext (public)

MPI-I-93-144.pdf
(Any fulltext), 10MB

Supplementary Material (public)

There is no public supplementary material available

Citation

Bilardi, G., Chaudhuri, S., Dubhashi, D. P., & Mehlhorn, K.(1993). A lower bound for area-universal graphs (MPI-I-93-144). Saarbrücken: Max-Planck-Institut für Informatik.

Cite as: https://hdl.handle.net/11858/00-001M-0000-0014-B75A-4

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)$.