Presentation	2001/11/19 Layout of Trees into Rectangular Grids of Small Width Akira MATSUBAYASHI,
PDF Download Page	PDF download Page Link
Abstract(in Japanese)	(See Japanese page)
Abstract(in English)	The problem of laying out graphs into rectangular grids with minimum area is a fundamental formulation for the problems such as VLSI layout and efficient computation on a parallel computer system whose processors aare interconnected by a mesh network. In this paper, we show that under Manhattan routing model and edge-disjoint routing model, an N-vertex binary tree T can be laid out into a grid of area O((k+α)/(1+α)N) and width k + α in polynomial time, where k is the minimum width of a grid into which T can be laid out, and α is an arbitrary integer with 0≨α≨√. We also show that the problem of determining, given a graph G and integers a and k, whether there exists a Manhattan layout of G into a grid of area a and width k is NP-complete even if G is restricted to a tree, and that the corresponding problem under edge-disjoint model is NP-complete even if G is restricted to an acyclic graph with maximum vertex degree at most 3 and k is restricted to an arbitrary fixed integer at least 3.
Keyword(in Japanese)	(See Japanese page)
Keyword(in English)	graph layout / VLSI layout / grid / tree
Paper #	CAS2001-74,CST2001-27
Date of Issue

Conference Information
Committee	CAS
Conference Date	2001/11/19(1days)
Place (in Japanese)	(See Japanese page)
Place (in English)
Topics (in Japanese)	(See Japanese page)
Topics (in English)
Chair
Vice Chair
Secretary
Assistant

Paper Information
Registration To	Circuits and Systems (CAS)
Language	ENG
Title (in Japanese)	(See Japanese page)
Sub Title (in Japanese)	(See Japanese page)
Title (in English)	Layout of Trees into Rectangular Grids of Small Width
Sub Title (in English)
Keyword(1)	graph layout
Keyword(2)	VLSI layout
Keyword(3)	grid
Keyword(4)	tree
1st Author's Name	Akira MATSUBAYASHI
1st Author's Affiliation	Faculty of Engineering, Kanagawa University()
Date	2001/11/19
Paper #	CAS2001-74,CST2001-27
Volume (vol)	vol.101
Number (no)	458
Page	pp.pp.-
#Pages	8
Date of Issue