VLSI Layout of Trees into Grids of Minimum Width

概要

論文の詳細を見る
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 O((k+α)/(1+α)N) and width k + α, where α is an arbitrary integer with 0 ≤ α ≤ √<N>, and the area is existentially optimal for any k ≤ 1 and N) and width k + α, where α is an arbitrary integer with 0 ≤ α ≤ α ≤ 0. This implies that α = Ω(k) is essential foralayout 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.
社団法人電子情報通信学会の論文
2004-05-01