Presentation	2005-01-19 Small Congestion Embedding of Separable Graphs into Grids of the Same Size Akira MATSUBAYASHI,
PDF Download Page	PDF download Page Link
Abstract(in Japanese)	(See Japanese page)
Abstract(in English)	In this paper we consider the problem of embedding a (guest) graph into a grid with the same number of nodes as those of the guest graph with minimum edge congestion. We show that a graph which has some efficient recursive separators can be embedded into a grid of the same size with small congestion. Our results imply that an N-node planar graph with maximum vertex degree Δ can be embedded into an N-node grid with congestion O(Δ^2logN), and if the graph is a tree, then it can be embedded into an N-node grid with congestion O(Δ). The congestion for trees is optimal within a constant factor, and the congestion for planar graphs is optimal within an O(min{Δ^2√, ΔlogN}) factor.
Keyword(in Japanese)	(See Japanese page)
Keyword(in English)	graph embedding / congestion / grid / separator
Paper #	CAS2004-63
Date of Issue

Conference Information
Committee	CAS
Conference Date	2005/1/12(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)	Small Congestion Embedding of Separable Graphs into Grids of the Same Size
Sub Title (in English)
Keyword(1)	graph embedding
Keyword(2)	congestion
Keyword(3)	grid
Keyword(4)	separator
1st Author's Name	Akira MATSUBAYASHI
1st Author's Affiliation	Division of Electrical Engineering and Computer Science, Kanazawa University()
Date	2005-01-19
Paper #	CAS2004-63
Volume (vol)	vol.104
Number (no)	555
Page	pp.pp.-
#Pages	6
Date of Issue