VLSI Layout of Trees into Grids of Minimum Width

Akira MATSUBAYASHI

VLSI Layout of Trees into Grids of Minimum Width

Akira MATSUBAYASHI

Full Text Views

0

Share
Cite this

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.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E87-A No.5 pp.1059-1069

Publication Date: 2004/05/01

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

Category

Cite this

Copy

Akira MATSUBAYASHI, "VLSI Layout of Trees into Grids of Minimum Width" in IEICE TRANSACTIONS on Fundamentals, vol. E87-A, no. 5, pp. 1059-1069, May 2004, doi: .
Abstract: 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.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1587/e87-a_5_1059/_p

Copy

@ARTICLE{e87-a_5_1059,
author={Akira MATSUBAYASHI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={VLSI Layout of Trees into Grids of Minimum Width},
year={2004},
volume={E87-A},
number={5},
pages={1059-1069},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={May},}

Copy

TY - JOUR
TI - VLSI Layout of Trees into Grids of Minimum Width
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1059
EP - 1069
AU - Akira MATSUBAYASHI
PY - 2004
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E87-A
IS - 5
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - May 2004
AB - 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.
ER -