圖形繪製是計算科學及工程中將關聯訊息視覺化常見的一種方法。在過去的研究中，科學家主要著重於設計靜態圖形的佈局，以達到較佳的資訊可讀性。直接將靜態圖形的佈局方法延伸到隨時間變化的動態圖形的每一個時間點，會無法維持時間及空間上的一致性，並且造成雜亂的視覺效果。
在這篇論文研究中，我們對於隨時間變化的圖形繪製提出了一個新的演算法能夠維持較佳的時間及空間上的一致性。藉由修改既有的圖形繪製演算法，產生具有時間及空間連續性的每個時間點的初始佈局，並且將標記重點的隨時間變化的圖形佈局以一個最佳化網格變形的問題來表達。藉由最佳化時間及空間上一致性的修件限制，維持連續時間點的圖形在時間及空間上的分佈一致且均勻。
我們的方法對於標記重點的隨時間變化圖形視覺化非常有效，對於重要性較高的結點，可以有效的防止其產生過多無意義的移動，助於使用者觀察其變化。

Graph drawing is a standard method to visualize relational information. Many previous approaches have been focused on the design of layout for static graphs to achieve good readability. Naively utilizing these approaches to layout individual time steps for time-varying graphs often fails to maintain spatiotemporal coherence, thus making it difficult for viewers to track the changes of graph. This situation is exacerbated by the ever-growing graph data we need to handle. To address this issue, we propose a new approach for time-varying graph drawing that achieves both spatial-temporal coherence and focus+context visualization. Our approach utilizes existing graph layout algorithms to produce the initial graph layout and formulates spatiotemporally coherent visualization of the time-varying graph as a deformation optimization problem. The optimization is achieved by incorporating spatiotemporal coherence constraints and adopting the concept of supergraphs to preserve spatiotemporally coherent content. Furthermore, the proposed deformation framework can achieve the compromise between aesthetic quality and dynamic stability for time-varying graphs with interactive performance. Our method is very useful for multi-focus+context visualization of time-varying graphs, and can prevent the graph nodes of focus from having abrupt changes in size and location in the time sequence. Experiments demonstrate that our method can maintain good spatiotemporal coherence and produce stable results, thus providing a more engaging viewing experience for users.

[1] A. Noack. An energy model for visual graph clustering. In Proceedings of International Symposium on Graph Drawing, pages 425-436, 2004.
[2] C. Walshaw. A multilevel algorithm for force-directed graph drawing. In Proceedings of International Symposium on Graph Drawing. pages 31-55, 2001.
[3] C. Collberg, S. Kobourov, J. Nagra, J. Pitts, and K. Wampler. A system for graph-based visualization of the evolution of software. In Proceedings of ACM Symposium on Software Visualization, pages 77-86, 2003.
[4] C. Görg, P. Birke, M. Pohl, and S. Diehl. Dynamic graph drawing of sequences of orthogonal and hierarchical graphs. In Proceedings of International Symposium on Graph Drawing, pages 228-238, 2005.
[5] C. Muelder and K.-L. Ma. Rapid graph layout using space filling curves. IEEE Transactions on Visualization and Computer Graphics, 14(6):1301-1308, 2008.
[6] C. Muelder and K.-L. Ma, A treemap based method for rapid layout of large graphs. In Proceedings of IEEE Pacific Visualization Symposium, pages 231-238, 2008.
[7] C. Wang, H. Yu, and K.-L. Ma. Importance-driven time-varying data visualization. IEEE Transactions on Visualization and Computer Graphics, 14(6):1547-1554, 2008.
[8] D. Harel and Y. Koren. A fast multi-scale method for drawing large graphs. Journal of Graph Algorithms and Applications, pages 183-196, 2002.
[9] D. Harel and Y. Koren. Graph drawing by high-dimensional embedding. In Proceedings of International Symposium on Graph Drawing, pages 299-345, 2002.
[10] E. Gansner, Y. Koren, and S. North. Topological fisheye views for visualizing large graphs. In Proceedings of IEEE Symposium on Information Visualization, pages 175-182, 2004.
[11] E. R. Gansner, Y. Koren, and S. North. Graph drawing by stress majorization. In Proceedings of International Symposium on Graph Drawing, pages 239-250, 2005.
[12] F. van Ham and M. Wattenberg. Centrality based visualization of small world graphs. In Proceedings of Eurographics - IEEE VGTC Symposium on Visualization, pages 975-982, 2008.
[13] G. W. Furnas. Generalized fisheye views. ACM SIGCHI Bulletin, 17(4):16-23, 1986.
[14] G. W. Furnas. A fisheye follow-up: Further reflections on focus+context. In Proceedings of ACM SIGCHI Conference on Human Factors in Computing Systems, pages 999-1008, 2006.
[15] G. Kuman and M. Garland. Visual exploration of complex time-varying graphs. IEEE Transactions on Visualization and Computer Graphics, 12(5):805-812, 2006.
[16] I. Herman, G. Melancon, and M. S. Marshall. Graph visualization and navigation in information visualization: A survey. IEEE Transactions on Visualization and Computer Graphics, 6(1):24-43, 2000.

[17] J. R. Shewchuk. Triangle: Engineering a 2d quality mesh generator and delaunay triangulator. In Proceedings of ACM Workshop on Applied Computational Geometry, pages 203-222, 1996.
[18] J. D. Cohen. Drawing graphs to convey proximity: An incremental arrangement method. ACM Transactions on Computer-Human Interaction, 4(3):197-229, 1997.
[19] J. Díaz, J. Petit, and M. Serna. A survey of graph layout problems. ACM Computing Surveys, 34(3):313-356, 2002.
[20] K. Sugiyama, S. Tagawa, and M. Toda. Methods for visual understanding of hierarchical system structures. IEEE Transactions on Systems, Man, and Cybernetics, 11(2):109-125, 1989.
[21] K.-P. Yee, D. Fisher, R. Dhamija, and M. Hearst. Animated exploration of dynamic graphs with radial layout. In Proceedings of IEEE Symposium on Information Visualization, pages 43-50, 2001.
[22] L. Buatois, G. Caumon, and B. Lévy. Concurrent number cruncher: A GPU implementation of a general sparse linear solver. International Journal of Parallel, Emergent and Distributed Systems, 24(3):205-223, 2009.
[23] M. Sarkar and M. H. Brown. Graphical fisheye views of graphs. In Proceedings of ACM SIGCHI Conference on Human Factors in Computing Systems, pages 83-91, 1992
[24] M. Sarkar, S. S. Snibbe, O. J. Tversky, and S. P. Reiss. Stretching the rubber sheet: A metaphor for viewing large layouts on small screens. In Proceedings of ACM Symposium on User Interface Software and Technology, pages 81-91, 1993.

[25] P. Eades. A heuristic for graph drawing. Congressus Numerantium, 42:149-160, 1984.
[26] P. Gajer ad S. G. Kobourov. GRIP: Graph drawing with intelligent placement. In Proceedings of International Symposium on Graph Drawing, pages 222-228, 2001.
[27] S. Wasserman and K. Faust. Social Network Analysis: Methods and Applications. Cambridge University Press, 1994.
[28] S. C. North. Incremental layout in DynaDAG. In Proceedings of International Symposium on Graph Drawing, pages 409-418, 1996.
[29] S. Diehl, C. Görg, and A. Kerren. Preserving the mental map using foresighted layout. In Proceedings of Eurographics - IEEE TCVG Symposium on Visualization, pages 175-184, 2001.
[30] S. Diehl and C. Görg. Graphs, they are changing. In Proceedings of International Symposium on Graph Drawing, pages 23-30, 2002.
[31] S. Hachul and M. Jünger. Drawing large graphs with a potential-field-based multilevel algorithm. In Proceedings of International Symposium on Graph Drawing, pages 285-295, 2005.
[32] S. Hachul and M. Jünger. An experimental comparison of fast algorithms for drawing general large graphs. In Proceedings of International Symposium on Graph Drawing, pages 235-250, 2006.
[33] T. Kamada and S. Kawai. An algorithm for drawing general undirected graphs. Information Processing Letters, 31(1):7-15, 1989.
[34] T. M. J. Fruchterman and E. M. Reingold. Graph drawing by force-directed placement. Software - Practice and Experience, 21(11):1129-1164, 1991.
[35] T. Munzner. H3: Laying out large directed graphs in 3D hyperbolic space. In Proceedings of IEEE Symposium on Information Visualization, pages 2-10, 1997.
[36] U. Brandes and D. Wagner. A Bayesian paradigm for dynamic graph layout. In Proceedings of International Symposium on Graph Drawing, pages 236-247, 1997.
[37] Y. Koren, L. Carmel, and D. Harel. ACE: A fast multiscale eigenvectors computation for drawing huge graphs. In Proceedings of IEEE Symposium on Information Visualization, pages 137-144, 2002.
[38] Y. Frishman and A. Tal. Dynamic drawing of clustered graphs. In Proceedings of IEEE Symposium on Information Visualization, pages 191-198, 2004.
[39] Y. Frishman and A. Tal. Multi-level graph layout on the GPU. IEEE Transactions on Visualization and Computer Graphics, 13(6):1310-1319, 2007.
[40] Y. Frishman and A. Tal. Online dynamic graph drawing. In Proceedings of Eurographics - IEEE VGTC Symposium on Visualization, pages 75-82, 2007.
[41] Y.-S. Wang, T.-Y. Lee, and C.-L. Tai. Focus+context visualization with distortion minimization. IEEE Transactions on Visualization and Computer Graphics, 14(6):1731-1738, 2008.
[42] Y.-S. Wang, H. Fu, O. Sorkine, T.-Y. Lee, and H.-P. Seidel. Motion-aware temporal coherence for video resizing. ACM Transactions on Graphics, 28(5), 2009.

[43] Y.-S. Wang, C. Wang, T.-Y. Lee, and K.-L. Ma. Feature-preserving volume data reduction and focus+context visualization. IEEE Transactions on Visualization and Computer Graphics, 2011. To Appear.