Master_thesis.dvi

10 第 2 章 グラフレイアウト 2.1 グラフレイアウト手法 第 1 章で述べたような審美的基準に沿ってグラフをレイアウトするには、どのよう なノード配置が審美的基準を最適化するかを探索する。 しかし、総当り的に探索することは組み合わせ的に膨大な数となり多くの場合 NP 困 難であるため、ユーザによるインタラクティブな情報獲得を支援するためには、近似 的な最適解を短時間で求めるためのヒューリスティ ックな手法が求められる。 そのための手法は大まかに 2 種類に分類され、グラフ理論をベースにしたアルゴリ ズム的アプローチ、物理モデルをベースとしたモデル的アプローチがある。[2] 2.2 アルゴリズム的アプローチ 主にグラフアルゴリズムや、計算幾何、離散数学などの理論的手法を利用し、あら かじめ用意された審美的基準を拘束条件としてこれを準最適化するように設計された 高速なア