グラフの埋め込みに必要な面積と交差数の兼ね合いについて

木本 隆  丸岡 章  木村 正行  

誌名
電子情報通信学会論文誌 D   Vol.J66-D   No.7   pp.834-840
発行日: 1983/07/25
Online ISSN: 
DOI: 
Print ISSN: 0913-5713
論文種別: 論文
専門分野: 
キーワード: 


本文: PDF(507.5KB)>>
論文を購入




あらまし: 
近年の集積回路技術の急速な進歩にともない,大規模な論理回路を比較的容易に実現できるようになった.これにともないVLSIチップ上に,回路をいかに効率よく埋め込むかという重要な問題が生じてくる.この問題はグラフの埋め込み問題として定式化できるが,これまでは埋め込みの良さの尺度として,埋め込みに必要な面積がとりあげられていた.本論文では,この尺度として埋め込みに必要な面積Aと配線の交差数Cの積AC をとりあげ,回路を表わす種々のグラフを,チップを表わす格子平面に埋め込む際に必要となるAC を評価した.その結果,(1)N個の頂点からなる平面グラフのクラスに対してACθN2)が,N個の頂点からなるスーパーコンセントレーターのクラスに対してACθN4)が成立する,(2)N個の頂点からなる平面グラフをONlog2N)の面積で格子平面に埋め込むValiantのアルゴリズムでは,交差数がΩN/log2N)となる平面グラフのクラスが存在する,等が明らかとなった.