平面グラフの最大重み窓問題

スポンサーリンク

概要

論文の詳細を見る
平面グラフの描写は描かれている平面をいくつかの領域に分割しているが,それらの領域のそれぞれを面と呼び,各面の周を構成しているような部分グラフを窓と呼ぶ.平面グラフGの描写中に存在し得る各窓Wについて,その頂点と辺の重みの総和を窓Wの重みと呼ぶ.描写に現れ得るすべての窓のうちで重みが最大のものを,Gの最大重み窓と呼ぶ.本論文では最大重み窓をもつ描写を求める問題について考える.グラフが2連結である場合およびすべての重みが非負であり2連結とは限らない場合についての結果は既に得られていた.本論文では実数の重みの与えられた任意の平面グラフに対して,O(n+e)時間で最大重み窓をもつ描写を求めることができることを示す.この結果はLSIや印刷基板のレイアウト設計,ネットワークの図示などに応用をもち,また,グラフの極大平面化問題を解くことにも用いることができる.
社団法人電子情報通信学会の論文
1995-10-25

著者

関連論文

もっと見る

スポンサーリンク