文献

J-GLOBAL ID：200902241338115236   整理番号：09A0797616

固有楕円ポテンシャルを利用したラベル付きグラフ可視化の座標計算

Labeled Graph Drawing Based on the Individual Ellipsoidal Potentials

著者 (4件)： 松林達史 (NTT コミュニケーション科学基礎研) ,  山田武士 (NTT コミュニケーション科学基礎研) ,  藤村滋 (NTT サイバーソリューション研) ,  藤村考 (NTT サイバーソリューション研)
資料名： 情報処理学会論文誌トランザクション(CD-ROM)  (情報処理学会論文誌 Computer Vision and Applications(CD-ROM))
巻： 2008  号： 1  ページ： VOL.1NO.1,88-101  発行年： 2008年11月15日 
JST資料番号： L7379A  ISSN： 1882-7772  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 本研究では,ラベル付きグラフ可視化のための,ラベルどうしが重ならない効率的な可視化座標計算の手法を提案する。従来のラベル付きグラフ可視化の座標計算アルゴリズムはForce-directed法やバネモデルといった,ノードを“点”として扱う座標計算を行うために,文字列や,異なるサイズのラベルを扱う場合,ラベルどうしが重なってしまうという問題が生じる。ラベルの重なりを回避する手法はいくつか提案されているが,いずれの手法も可視化計算を行った後に,再び座標計算処理を必要とする。これ等の手法では大規模なグラフ可視化では計算量が莫大となり,さらに元の可視化結果を破壊してしまうという問題が生じる。そこで,各ノードの斥力項として,ラベルサイズに依存した固有楕円ポテンシャルを与え,さらに,点対称ポテンシャルと固有楕円ポテンシャルの関数の重ね合わせる手法を提案する。提案法により,メンタルマップを保ちつつ,かつ,局所的なラベルの重なりを回避できることを示した。(著者抄録)

シソーラス用語： 座標 ,  *グラフ ,  *可視化 ,  計算量 ,  ポテンシャル ,  重合せ ,  レイアウト ,  局所性 ,  楕円
準シソーラス用語： メンタルマップ ,  *ラベル付きグラフ ,  固有楕円ポテンシャル ,  座標計算

分類 (2件)： グラフ理論基礎  (IA02020S) ,  図形・画像処理一般  (JE04010I)

引用文献 (8件)：

• Kamada, T. and Kawai, S.: An algorithm for drawing general undirected graphs, Information Processing Letters, Vol.12, No.31, pp. 7-15(1989).
• Fruchterman, T. M. J. and Reingold, E. M.: Graph Drawing by Force-directed Placement, Software — Practice and Experience, Vol.11, No.21, pp. 1129-1164(1991).
• Ebner, D., Klau, G. W. and Weiskircher, R.: Label Number Maximization in the Slider Model, Proc. Graph Drawing, New York, pp. 144-154(2004).
• Theophil, S. and Sch ̇ odel, A.: An Efficient Algorithm for ScatterChart Labeling, Proc. National Conference on AAAI, Boston, Massachusetts, USA (July 2006).
• Misue, K., Eades, P., Lai, W. and Sugiyama, K: Layout Adjustment and the Mental Map, Journal of Visual Languages and Computing, Vol.6, No.2, pp. 183-210(1995).

タイトルに関連する用語 (8件)： 固有 ,  楕円 ,  ポテンシャル ,  ラベル ,  グラフ ,  可視化 ,  座標 ,  計算