all possible aspect ratio can be obtained with increase of area within a small constant factor. We show that an N-vertex tree with layout-width k (i.e., the minimum width of a grid into which the tree can be laid out is k) can be laid out into a grid of area O(N) and width O(k). For binary tree layouts, we give a detailed trade-off between area and width: an N-vertex binary tree with layout-width k can be laid out into area and width k + α, where α is an arbitrary integer with 0 α , and the area is existentially optimal for any k 1 and α 0. This implies that α = Ω(k) is essential for a layout of a graph into optimal area. The layouts proposed here can be constructed in polynomial time. We also show that the problem of laying out a given graph G into given area and width, or equivalently, into given length and width is NP-hard even if G is restricted to a binary tree." />


VLSI Layout of Trees into Grids of Minimum Width

Akira MATSUBAYASHI  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E87-A   No.5   pp.1059-1069
Publication Date: 2004/05/01
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
VLSI layout,  graph layout,  graph embedding,  grid,  aspect ratio,  

Full Text: PDF>>
Buy this Article




Summary: 
In this paper we consider the VLSI layout (i.e., Manhattan layout) of graphs into grids with minimum width (i.e., the length of the shorter side of a grid) as well as with minimum area. The layouts into minimum area and minimum width are equivalent to those with the largest possible aspect ratio of a minimum area layout. Thus such a layout has a merit that, by "folding" the layout, a layout of all possible aspect ratio can be obtained with increase of area within a small constant factor. We show that an N-vertex tree with layout-width k (i.e., the minimum width of a grid into which the tree can be laid out is k) can be laid out into a grid of area O(N) and width O(k). For binary tree layouts, we give a detailed trade-off between area and width: an N-vertex binary tree with layout-width k can be laid out into area and width k + α, where α is an arbitrary integer with 0 α , and the area is existentially optimal for any k 1 and α 0. This implies that α = Ω(k) is essential for a layout of a graph into optimal area. The layouts proposed here can be constructed in polynomial time. We also show that the problem of laying out a given graph G into given area and width, or equivalently, into given length and width is NP-hard even if G is restricted to a binary tree.