著者

松林 達史 山田 武士 藤村 滋 藤村 考

出版者

情報処理学会

雑誌

情報処理学会論文誌数理モデル化と応用(TOM) (ISSN:18827780)

巻号頁・発行日

vol.1, no.1, pp.88-101, 2008-09-26

被引用文献数

1

---

本研究では,ラベル付きグラフ可視化のための,ラベルどうしが重ならない効率的な可視化座標計算の手法を提案する.従来のラベル付きグラフ可視化の座標計算アルゴリズムはForce-directed法やバネモデルといった,ノードを"点"として扱う座標計算を行うために,文字列や,異なるサイズのラベルを扱う場合,ラベルどうしが重なってしまうという問題が生じる.ラベルの重なりを回避する手法はいくつか提案されているが,いずれの手法も可視化計算を行った後に,再び座標計算処理を必要とする.これ等の手法では大規模なグラフ可視化では計算量が莫大となり,さらに元の可視化結果を破壊してしまうという問題が生じる.そこで,各ノードの斥力項として,ラベルサイズに依存した固有楕円ポテンシャルを与え,さらに,点対称ポテンシャルと固有楕円ポテンシャルの関数の重ね合わせる手法を提案する.提案法により,メンタルマップを保ちつつ,かつ,局所的なラベルの重なりを回避できることを示した.We present a new graph layout algorithm for a graph with node labels. The proposed algorithm can generate a graph layout efficiently avoiding overlapping of node labels. Most of the conventional algorithms such as force-directed and spring methods compute node positions by treating nodes as "points", and thus may cause node overlapping when strings or labels with various sizes are added to the nodes. Most of the conventional approaches to solve this problem require an initial graph layout creation phase without considering label sizes and a separate layout adjustment phase for overlap removal as its post processing. These methods are not suitable for a large-scale graph layout, because their computational costs are high and they may even destroy the initial graph layout. The proposed algorithm gives an individually different ellipsoidal potential to each node depending on its label size as well as a common point-symmetric potential, and the combination of these two potentials defines the repulsion force. This enables an efficient graph layout that can avoid local node overlaps while maintaining the mental map.