Abstract

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 Trans- fer Mode) switches. Our results improve on the existing area bounds for these networks by factors of up to three.