辺がラベルをもつ無向グラフの描画法

摘要

Gを連結な無向グラフとし,その各辺が,あらかじめ決められたサイズのラベルをもつものとする.辺がラベルをもつ無向グラフの描画法としてこれまで主に検討されてきたアプローチは,まずラベルの情報を特に考慮せずにグラフの頂点と辺を描き,次に適切な位置に辺のラベルを配置するというものであった.しかしこのようなアプローチでは,グラフが密である場合やラベルのサイズが大きい場合に,配置できないラベルが多く残ることがある.そこで本論文では,各辺のラベルの配置位置を考慮しながら頂点や辺の位置を決定するグラフ描画アルゴリズムを提案する.そして,この別さで得られる描画に対してラベル配置アルゴリズムを実行すれば,既存の(ラベルをもたないグラフを描画対象とした)グラフ描画アルゴリズムで得られる描画に対して同じことを行う場合に比べ,ラベル配置率を大幅に改善できることを計算機実験により示す.