EFFICIENT PLANAR EMBEDDING OF TREES FOR VLSI LAYOUTS.

This paper examines the use of planar polygonal partitioning schemes for embedding tree structures. Two layout designs based on recursive square and triangular decompositions are described for trees having branching factors of k**2 and k**2 minus 1, where k is an integer. The former design allocates the same amount of area to nodes at all levels and requires a total area linear in the number N of nodes in the tree. The latter design assigns increasing area to nodes closer to the root and requires a total area of 0 left bracket N(k**2/k**2 minus 1 logN right bracket . The longest interconnection has a length of 0(Area(N)) in each case.