VLSI LAYOUTS OF COMPLETE GRAPHS AND STAR GRAPHS

In this paper, we present efficient layouts for complete graphs and st ar graphs. We show that an N-node complete graph can be optimally laid out using [N-2/4] tracks for a colinear layout, and can be laid out i n N-4/16 + o(N-4) area for a 2D layout. We also show that an N-node st ar graph can be laid out in N-2/16 + o(N-2) area, which is smaller tha n any possible layout of a similar-size hypercube. This solves an open question posed by Akers and Krishnamurthy in 1986. Both the layouts o f complete graphs and star graphs are optimal within a factor 1 + o(1) . (C) 1998 Published by Elsevier Science B.V. All rights reserved.