摘要
图可视化技术是可视化研究的重要内容,近年来大图的绘制问题一直是图可视化技术的焦点。为此,提出了一种快速多层次算法用于解决大图绘制问题。采用多层次方法作为算法的框架,以FR力导向算法的变体结合质心算法以及四叉树空间分解等方法对单层布局进行优化。另外,还使用了约束规范化和能量模型2种加速方法。实验表明,该算法具有高效的性能和良好的布局效果。其效率非常高,在单核CPU下,可以在大约5 s内很好地绘制出10 000个顶点的图。并与几种经典的算法进行了比较,也证明了该算法的有效性和实用性。此外,该算法易于实现,可被轻易推广到其他布局算法上,以加速其运算。
Graph visualization technology is an important part of visualization research.The drawing of large graphs has been the focus of graph visualization technology in recent years.This paper proposes a fast multilevel algorithm for solving large graph drawing problems.The algorithm uses a multilevel method as the framework of the algorithm.The present study uses a FR force-directed algorithm variant combined with centroid algorithm and quad-tree space decomposition method to refine the single-level layouts.Also,energy-model and constraint-normalization are used.Experiments show that the algorithm has high performance and good layout effect.The algorithm is of high efficiency,and under a single-core CPU,it can effectively draw a graph of 10,000 vertices in about 5 seconds.Through comparison with several classical algorithms,the effectiveness and practicability of the algorithm was proved.In addition,the algorithm is easy to implement and can be easily generalized to other layout algorithms to speed up its operations.
作者
张野
王松
吴亚东
ZHANG Ye;WANG Song;WU Ya-dong(College of Computer Science and Technology,Southwest University of Science and Technology,Mianyang Sichuan 621010,China)
出处
《图学学报》
CSCD
北大核心
2019年第1期78-86,共9页
Journal of Graphics
基金
国家重点研究计划项目(2016QY04W0801)
西南科技大学研究生创新基金项目(17ycx052)
关键词
快速多层次算法
大图绘制
图可视化
图布局算法
fast multilevel algorithm
drawing large graphs
graph visualization
graph layout algorithm
