グラフのレイアウトで参考になるアルゴリズムはありませんか？

質問

グラフのレイアウトで参考になるアルゴリズムはありませんか？
ノード間に関係を表すエッジが複数あるとしてランダムに表示されたノードを関係あるものを近くに表示させたいと思っています。
バネモデルなどを使った力学的モデルを使った配置の考え方は見つけたのですが、実行してみるとかなり遅くなってしまいます。
別に見つけた商用ライブラリyFilesのサンプルを使ってみるとあっという間に終わり何か別種のアルゴリズムを使っているとしか思えません。
ttp://www.yworks.com/en/products_yed_about.htm
何か考え方のヒントになるようなものでも助かるので何かないでしょうか。

回答No.1

kacchann

sunのjdk付属のデモに、「ばね」アルゴリズム(?)を使用した
グラフ描画アプレットがありますが、
ここで使われているアルゴリズムを使用して、
とりあえず簡易実験してみました。
---

実験内容
・ノード数---50
・再計算回数(※最終レイアウト決定に要する計算回数)
　---100回(または200回)の"決め打ち"
・PenIII(500MHz)のマシン

結果(※描画に要した時間は含まれない)
再計算100回 0.05～0.06秒
再計算200回 0.16～0.22秒