欢迎访问《图学学报》 分享到：
图学学报

图学学报

• 专论：第21届中国计算机辅助设计与图形学暨第11届全国几何设计与计算机联合会议(CAD&CG GDC 2018 桂林) • 上一篇    下一篇

FMR：基于 FR 的快速多层次算法

  

  1. 西南科技大学计算机科学与技术学院，四川 绵阳 621010
  • 出版日期:2019-02-28 发布日期:2019-02-27
  • 基金资助:
    国家重点研究计划项目(2016QY04W0801)；西南科技大学研究生创新基金项目(17ycx052)

FMR: A Fast Multilevel Algorithm Based on FR

  1. College of Computer Science and Technology, Southwest University of Science and Technology, Mianyang Sichuan 621010, China
  • Online:2019-02-28 Published:2019-02-27

PDF (PC)

164

摘要： 图可视化技术是可视化研究的重要内容，近年来大图的绘制问题一直是图可视化 技术的焦点。为此，提出了一种快速多层次算法用于解决大图绘制问题。采用多层次方法作为 算法的框架，以 FR 力导向算法的变体结合质心算法以及四叉树空间分解等方法对单层布局进 行优化。另外，还使用了约束规范化和能量模型 2 种加速方法。实验表明，该算法具有高效的 性能和良好的布局效果。其效率非常高，在单核 CPU 下，可以在大约 5 s 内很好地绘制出 10 000 个顶点的图。并与几种经典的算法进行了比较，也证明了该算法的有效性和实用性。此外，该 算法易于实现，可被轻易推广到其他布局算法上，以加速其运算。

关键词: 快速多层次算法, 大图绘制, 图可视化, 图布局算法

Abstract: 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.

Key words: fast multilevel algorithm, drawing large graphs, graph visualization, graph layout algorithm