DIAVIS-wiki

• バックアップ一覧
• バックアップ を表示
• Graph Drawing は削除されています。
  • 1 (2009-01-02 (金) 16:07:34)
  • 2 (2009-01-02 (金) 19:44:15)
  • 3 (2009-01-02 (金) 22:52:08)

[[FrontPage]]

:private
#contents

*情報源 [#pab2e242]
:graph theory on wikipedia|http://en.wikipedia.org/wiki/Graph_theory
:graph drawing on wikipedia|http://en.wikipedia.org/wiki/Graph_drawing
:Force-based algorithms|http://en.wikipedia.org/wiki/Force-based_algorithms

*書籍 [#q57d3c8b]
**Giuseppe Di Battista, Peter Eades, Roberto Tamassia, Ioannis G. Tollis [#u08e3c3f]
-Graph Drawing
-Algorithms for the Visualization of Graphs
-Prentice Hall, 1999
-ISBN: 0-13-30-1615-3
引用済み．


*レイアウトアルゴリズム [#bbb6f43d]
**アルゴリズム的 [#e70f5b35]
**モデル的 [#c49de93d]
***遺伝子 [#g607d2f6]
***力学（Force-Directed Techniques） [#f4863f6f]

-Advantage(Pro):
--実装がシンプル relatively simple to implement
--試行錯誤的な改善が簡単に追加できる heuristic improvements easily added
--smooth evolution of the drawing into the final configuration helps preserving the user’s mental map
--can be extended to 3D
--often able to detect and display symmetries
--works well in practice for small graphs with regular structure
-- limted constraint satisfaction capability
-Disadvantage(Con):
--slow running time
--few theoretical results on the quality of the drawings produced
--diffcult to extend to orthogonal and polyline drawings
--limited constraint satisfaction capability


: [Kamada Kawai 89]|
n the forces try to place vertices so that
their geometric distance in the
drawing is equal to their
graph-theoretic distance
n for each pair of vertices (u,v) use a
spring with natural length dist(u,v)
: [Fruchterman Reingold 90]|
n system of forces similar to that of
subatomic particles and celestial
bodies
n given drawing region acts as wall
n n-body simulation
: [Davidson Harel 89]|
n energy function takes into account
vertex distribution, edge-lengths, and
edge-crossings
n given drawing region acts as wall
n simulated annealing

****磁力 [#xe5d14b3]
-Kozo Sugiyama and Kazuo Misue: Graph drawing by the magnetic spring model, J. of Visual Languages and Computing, vol.6, no.3, pp.217-231, 1995.

*API [#p305a966]
:JUNG|http://jung.sourceforge.net/
:prefuse|http://prefuse.org/

:まとめサイト|http://www.dmoz.org/Science/Math/Combinatorics/Software/Graph_Drawing//

*参考サイト [#w1d28bca]
-http://graphdrawing.org/index.html
:チュートリアル|http://graphdrawing.org/literature/gd-constraints.pdf