一种用于Marching-Graph图形绘制的快速收敛布局算法
作者:

Fast Convergence Layout Algorithm for Drawing Graphs in Marching-Graph
  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [14]
  • |
  • 相似文献 [20]
  • | | |
  • 文章评论
    摘要:

    Marching-Graph是一种将图形隐喻技术和空间隐喻技术集成为一体的新的可视化方法.它为用户提供了高度可交互性地图,使用户可访问那些具有地理属性的信息的逻辑结构.它通过有效的人图交互和跨空间浏览为用户提供了一种可视分析和挖掘未知信息的机制,而不是将已知的信息呈现在地图上.然而,传统的力导向布局算法在达到力量均衡配置方面非常慢.为使一个图形布局收敛,它们通常需花费几十秒的时间.因此,当用户快速行进于地理区间时,那些力导向布局算法就不能满足快速绘制一系列图形的要求.提出了一种快速收敛布局方法,当用户在Marching-Graph中通过力导向布局逐步探究一系列图形时,它可以加速交互时间.通过结合辐射树绘图技术和力导向图形绘制方法来取得能量最小化的快速收敛.

    Abstract:

    Marching-Graph is a new visualization that integrates the graph metaphor and the spatial metaphor into a single visualization. It provides users with highly interactive maps for accessing the logical structures of information that has the geographical attributes. Instead of presenting known facts onto maps, it provides a mechanism for users to visually analyze and seek unknown knowledge through effective human-map interaction and navigation across different spaces. However, the traditional force-directed layout algorithms are very slow in reaching an equilibrium configuration of forces. They usually spend tens of seconds making the layout of a graph converge. Thus, those force-directed layout algorithms can not satisfy the requirement for drawing a sequence of graphs rapidly, while the users are quickly marching through the geographic regions. This paper proposes a fast convergence layout method that speeds up the interaction time while users are progressively exploring a sequence of graphs through a series of force-directed layouts in Marching-Graph. It essentially combines a radial tree drawing method and a force-directed graph drawing method to achieve the fast convergence of energy minimization.

    参考文献
    [1]Fuchs G,Schumann H.Visualizing abstract data on maps.In:Proc.of the Information Visualization,8th Int'l Conf.on Information Visualization (IV 2004).London,2004.139-144.
    [2]Keim DA,Noth SC,Panse C,Schneidewind J.Visualizing geographic information:VisualPoints vs CartoDraw.Information Visualization,2003,2:58-67.
    [3]Andrienko GL,Andrienko NV.Interactive maps for visual data exploration.Int'l Journal for Geographical Information Science,1999,13(4):355-374.
    [4]Kreuseler M,Schumann H.A flexible approach for visual data mining.IEEE Trans.on Visualization and Computer Graphics,2002,8(1):39-51.
    [5]Quan W,Huang ML.Dynamic visualization of spatially referenced information.In:Proc.of the Int'l Symp.on Visual Computing.LNCS 3804,2005.642-646.
    [6]Davidson R,Harel D.Drawing graphs nicely using simulated annealing.ACM Trans.on Graphics,1996,15(4):301-331.
    [7]Eades P.A heuristic for graph drawing.Congressus Numerantium,1984,42:149-160.
    [8]Frick A,Ludwig A,Mehldau H.A fast adaptive layout algorithm for undirected graphs.In:Proc.of the Symp.Graph Drawing GD'93.1994.389-403.
    [9]Fruchterman T,Reingold E.Graph drawing by force-directed placement.Software-Practice & Experience,1991,21:1129-1164.
    [10]Huang ML,Eades P,Wang JH.On-line animated visualization of huge graphs using a modified spring algorithm.Journal of Visual Languages and Computing,1998,9:623-645.
    [11]Battista GD,Eades P,Tamassia R,Tollis IG.Graph Drawing:Algorithms for The Visualization Of Graphs.Englewood Cliffs:Prentice-Hall,1999.
    [12]Eades P.Drawing free trees.In:Bulletin of the Institute of Combinatorics and Its Applications.1992.10-36.
    [13]Yee KP,Fisher D,Dhamija R,Hearst MA.Animated exploration of dynamic graphs with radial layout.In:Proc.of the InfoVis'01.2001.43-50.
    [14]Barnes JE,Hut P.A hierarchical O(N log N) force-calculation algorithm.Nature,1986,324(6270):446-449.
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

全 武,黄茂林.一种用于Marching-Graph图形绘制的快速收敛布局算法.软件学报,2008,19(8):1920-1932

复制
分享
文章指标
  • 点击次数:8636
  • 下载次数: 7918
  • HTML阅读次数: 0
  • 引用次数: 0
历史
  • 收稿日期:2008-04-18
  • 最后修改日期:2008-01-08
文章二维码
您是第19788084位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号