抄録
グラフ配置は, オブジェクト間の関係を表現するための情報視覚化技術である.一般無向グラフなどの複雑なグラフは, 静的に配置することが困難であるため, 対話的グラフ配置がしばしば重要となる.本論文では, 一般無向グラフの対話的配置の新しいアプローチを提案する.本アプローチの基本アイデアは, 高次元空間における静的なグラフ配置を用いて, ユーザの操作に応じて2次元グラフ配置を動的に決定するというものである.本アプローチに基づいて構築する手法は, 以下の2つの特徴を持つ.(1)ユーザの操作に応じて, 2次元グラフ配置をきわめて高速に計算する.(2)ユーザによるノードのドラッグ操作に合わせて, それに関連の深いノードを中心に移動を行う.本手法では, 高次元グラフ配置を求めるために, 固有ベクトル計算に基づく多次元尺度法を用い, 2次元グラフ配置を得るために, 制約解消によって決定される適切な2次元平面への射影を行うという方法を採用する.
Graph layout is an information visualization technology for illustrating relations between objects. Interactive graph layout is often important since it is difficult to statically lay out complex graphs such as general undirected graphs. In this paper, we propose a novel approach to the interactive layout of general undirected graphs. The basic idea behind our approach is to use static graph layouts in high-dimensional spaces to dynamically find two-dimensional layouts according to user interaction. The resulting method that we present exhibits the following two characteristics: (1) it efficiently updates two-dimensional graph layouts during user interaction; (2) it follows users' node dragging operations by actively moving other closely related nodes. Our method adopts eigenvector-based multidimensional scaling to compute high-dimensional graph layouts, and performs constraint satisfaction to determine appropriate two-dimensional planes onto which the high-dimensional layouts will be projected.
