Compact grid layouts of multi-level networks

S. Muthukrishnan, Mike Paterson, Suleyman Cenk Sahinalp, Torsten Suel

Research output: Contribution to journalConference articlepeer-review

12 Scopus citations


We consider the problem of generating layouts of multi-level networks, in particular, switching, sorting, and interconnection networks, as compactly as possible on VLSI grids. Besides traditional interest in these problems motivated by interconnection topologies in parallel computing and switching circuits in telecommunications, there is renewed interest in such layouts in the context of ATM (Asynchronous Transfer Mode) switches. Our results improve on the existing area bounds for these networks by factors of up to three.

Original languageEnglish (US)
Pages (from-to)455-463
Number of pages9
JournalConference Proceedings of the Annual ACM Symposium on Theory of Computing
StatePublished - 1999
Externally publishedYes
EventProceedings of the 1999 31st Annual ACM Symposium on Theory of Computing - FCRC '99 - Atlanta, GA, USA
Duration: May 1 1999May 4 1999

All Science Journal Classification (ASJC) codes

  • Software


Dive into the research topics of 'Compact grid layouts of multi-level networks'. Together they form a unique fingerprint.

Cite this