力学モデル (グラフ描画アルゴリズム)
いくつかの対話的なグラフ描画ツールでは、ユーザがノードを引っ張ることができ、それが平衡状態にもどる様子を見ることができる。これらは、動的なグラフ描画システムや、オンラインアルゴリズムを用いる場合に有用である。
強い理論的な基盤がある。 この項目で実装例として紹介しているような、シンプルだがアドホックなアルゴリズムは文章や実用においてよく現れていたが、それと同時に、より合理的なアプローチが注目されるようになった。 統計学では1930年代から似たような問題をmultidimensional scaling (MDS) で解いていたし、物理学には多体問題 に関連した研究については長い歴史を持っている。このことから、このような問題に対しては極めて成熟したアプローチをもっている。 一例として、metric MDS に対する stress majorization法は、以上で説明したグラフ描画に応用できる。 この方法で一様収束することが証明されている。一様収束は、配置が必ず最終的に極小に到達し、停止することを保証するので重要である。減衰による方法(以下の擬似コードでの実装例のような場合)は、アルゴリズムは停止するが、真の極小に到達したことを保証するものではない。
しかし、以下のような短所もある。
時間がかかる。 典型的なアルゴリズムでは、入力グラフのノード数 V に対して O(V)程度の時間が必要だと考えられている。これは、必要な繰り返しの数が O(V) と見積もることができ、またそれぞれの繰り返しで、すべてのノードの組み合わせが巡回され、相互作用力を計算する必要があると考えられるからである。この問題は多体問題の難しさに関連している。しかし、相互作用力は近接作用なので、ただ隣の頂点のみが考慮されるようにグラフを分割することができる。大きいサイズのグラフのレイアウトのための一般的なテクニックには、high-dimensional embeddingや multi-layer drawing など、多体問題で使われているものが使える。例えば、FADE法を用いたBarnes–Hut simulationでは、繰り返しあたりの計算量が O(V log V) まで高速化できる。大雑把に考えて、数秒で描画できるノード数は最大で1,000ノード(標準的な、繰り返しあたり V になる方法)、 100,000ノード(高速化した、V log Vになる方法) と見積もられる。