階層グラフ描画における道の移動処理を用いた頂点順序決定法

的場 郁典  増田 澄男  荒木 徹也  斎藤 寿樹  山口 一章  

誌名
電子情報通信学会論文誌 A   Vol.J98-A   No.1   pp.152-164
発行日: 2015/01/01
Online ISSN: 1881-0195
DOI: 
論文種別: 論文
専門分野: グラフとネットワーク
キーワード: 
階層グラフ,  描画,  発見的手法,  頂点順序,  辺交差,  

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

 | 正誤(2015年12月1日公開)


あらまし: 
階層グラフの描画を求める際に,各階層における頂点配置順序を,辺交差数が少なくなるように決定するための新しい発見的手法を提案する.この方法は,階層グラフ中に次数1の頂点が存在する場合,着脱道と呼ぶ道を繰返し削除し,残ったグラフの頂点順序を決定した後に,削除した道を付け加えるという処理を行っている.また,次数1の頂点が存在するか否かにかかわらず,全頂点の配置を仮に定めた後,同じx座標をもつ頂点をまとめて移動する処理,及び辺交差が最多となっている道を見つけ,その上の頂点をまとめて移動する処理を行っている.疎な連結階層グラフを描画する場合,提案手法が,重心法に後処理を加えた従来の手法に比べ,辺交差数を削減できることを計算機実験によって示す.