臺灣博碩士論文加值系統

對於圖形繪製演算法而言，結合了多層次技巧以及力導向演算法的概念可以用來處理大型圖形。
然而對於原始大型圖形來說，由於頂點過多，所以必須要將頂點分群以便於了解。而分群不僅僅是讓使用者能輕易地對圖形了解，更是將圖形還原成原始要探討的問題時所重視的。因為對於原始問題而言，如果能夠將這些具有相同特性的實體聚集起來，可以讓使用者面對這些實體時，能一目瞭然，而簡化成易於處理的問題。
結合多層次技巧以及力導向演算法的方法雖然可以處理大型圖形，但是無法表達嵌入式叢集的概念，因為對於直線畫法而言，重視的是能快速的畫出圖形、以及較美觀的圖形。
所以在這裡提出了一個做法能夠在直線畫法中表現出嵌入式叢集的概念；而這個方法是架構在結合多層次技巧以及力導向演算法之上。由於多層次技巧的兩個步驟中，皆是為了便於力導向演算法的實作，故在其兩個步驟中，分別採用不同的做法以求達到可以利用力導向演算法在原始圖形中畫出具有嵌入式叢集的美感。利用我們提出的改良式多層次力導向演算法 ，可以在直線畫法中用來繪製大型叢集圖形。

To draw large clustered graphs, a force-directed method combine with the multilevel technique is presented. As a large graph containing a huge number of vertices, a key step in drawing such a graph is to group those entities which have attributes in common to reduce the original problem size.
Although the force-directed method which combines the multilevel technique can handle large graphs, it cannot express embedded clustered graphs very well. That is because straight-line drawing only cares about drawing graphs faster and nicer. We describe a method that can use straight-line drawing to show embedded clustered graphs. We alter the multilevel algorithm mentioned above to achieve the goal of aesthetic. As our experimental results indicate improved multilevel algorithm allows large clustered graphs to be drawn nicely.

第一章 緒論 6
第一節 前言 6
第二節 研究動機 10
第三節 問題簡介 12
第四節 論文架構 14
第二章 理論基礎 16
第一節 彈簧演算法 (Spring Algorithm) 16
第二節 多層次演算法 (Multilevel Algorithm) 22
第三章 研究內容 27
第一節 圖形加工 (Graph Coarsening) 27
第二節 圖形回覆 (Graph Uncoarsening) 43
第四章 實驗結果 47
第五章 結論與未來展望 57
第六章 參考文獻 60

[1] C. Walshaw, “A Multilevel Algorithm for Force-Directed Graph Drawing” Journal of Graph Algorithm and Applications, vol7, no. 3, pp. 253-285 (2003)
[2] S. Hachul and M. Junger, ”Drawing Large Graphs with a Potential-Field-Based Multilevel Algorithm” in the Proceedings of the 12th International Symposium on Graph Drawing 2004, (LNCS 3383) pp. 285-295 (2004)
[3] J. Chuang, C. Lin, and H. Yen, "Drawing Graphs with Nonuniform Nodes Using Potential Fields" in the Proceedings of the 11th International Symposium on Graph Drawing 2003, (LNCS 2912) pp. 460-465 (2003)
[4] P. Eades and M. Huang, “Navigating Cluster Graphs Using Force-Directed Methods” Journal of Graph Algorithm and Applications, vol4, no. 3, pp. 157-181 (2000)
[5] C. Walshaw and M. Cross, “Multilevel Mesh Partitioning for Heterogeneous Communication Networks” Technique Report 00/IM/57, University Greenwich, London SE10 9LS, UK, (2000)
[6] J. Fruchterman and M. Reingold, “Graph Drawing by Force-Directed Placement”Software - Practice and Experience, vol21, no. 11, pp. 1129-1164 (1991)
[7] G. Battista, P. Eades, and I. Tollis, “Graph Drawing Algorithm for Visualization of Graph” Prentice-Hall
[8] M. Kaufmann and D. Wagner, “Drawing Graphs” Springer
[9] P. Eades and Q. Feng, ”Multilevel Visualization of Clustered Graphs” in the Proceedings of the 4th International Symposium on Graph Drawing 1996, (LNCS 1190) pp. 101-112 (1996)
[10] B. Hendrickson and R. Leland “A Multilevel Algorithm for Partitioning Graph” in the Proceedings of the 1995 ACM/IEEE conference on Supercomputing, Vol0, no. 27, pp. 28 (1995)
[11] P. Eades, Q. Feng, X. Lin and H. Nagamochi, “Straight-Line Drawing Algorithm for Hierarchical Graph and Clustered Graph” in the Proceedings of the 4th International Symposium on Graph Drawing 1996, (LNCS 1190) pp. 113-127 (1996)
[12] G. Karypis and V. Kumar, “A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs” Technical Report 95-035, University of Minnesota, Department of Computer Science, Minneapolis, MN 55455, July (1995)
[13] Y. Chang “Electronical Design Automation EDA Lecture Note chap5” (2001)
[14] B. Kernighan and S. Lin, “An Efficient Heuristic Procedure for Partitioning Graphs” The Bell System Technical Journal, vol49, no. 2 pp. 291-308, (1990)
[15] R. Davidson and D. Harel “Drawing Graphs Nicely Using Simulated Annealing” ACM Transactions on Graphics, vol15, no. 4, pp. 301–331, (1996)
[16] M. Huang, P. Eades and J. Wang “On-line Animated Visualization of Huge Graphs Using a Modified Spring Algorithm” Journal of Visual Languages and Computing, vol9, no. vl980094, pp. 623-645 (1998)
[17] http://archive.dante.net/mbone/topo
[18] http://soy.dyndns.org/~peter/projects/fun/webmap/
[19] http://www.tomsaywer.com/gallery/