木の描画問題に対する0n)と0n2)時間アルゴリズム

土田 賢省  

誌名
電子情報通信学会論文誌 D   Vol.J76-D1   No.6   pp.237-246
発行日: 1993/06/25
Online ISSN: 
DOI: 
Print ISSN: 0915-1915
論文種別: 論文
専門分野: アルゴリズム,計算複雑性
キーワード: 
グラフ描画,  描画アルゴリズム,  ,  計算量,  

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




あらまし: 
本論文では一般の木を対象とした描画アルゴリズムを提案する.まず,2分木の描画に関する美的制約を拡張して,一般の木に対する美的制約を導入し,描画問題を定式化する.我々は木の幅を最小に描画することを最適基準にとる.次に描画問題の難しさを例を用いて説明し,これまで得られている理論的限界に関する結果を述べる.そして,指定された美的制約を満たしながら木の幅を最小にする二つのアルゴリズムを提案する.一つは,隣り合う部分木同士が1以上離れるという条件を含む美的制約のもとで,線形時間で描画を実現する.もう一つは,隣り合う部分木同士の重なりを与えられた数以下にするという条件を含む美的制約のもとで,0n2)時間で描画を実現する.更に,重なりの度合を制限しないときでも,0n2)であることが示される.これは,これまでに提案した同じ制約下のアルゴリズムの時間計算量が0n3),0n4)であるので,この問題に対する時間計算量の上界を引き下げる結果となっている.本論文のアルゴリズムは,木構造をしたプログラム図やシステム構成図などの表示に応用可能である.