基于图匹配的分层布局算法

摘要

In order to draw the undirected graph with big and even degrees, we propose a hierarchical layout algorithm based on graph matching ( GMH) .Firstly, a series of coarser and coarser graphs are generated by graph matching.Secondly, the optimal FR layout for the coarsest graph can be found cheaply.In the end, the layout on the coarser graphs is recursively prolonged to the finer graphs by the mass-center method.The new algorithm can not only advance the efficiency of graph visualization and improve the effect of layout, but also show a series of hierarchical graphs.%针对节点数目较大并且度数比较平均的无向图，根据分层扩展的思想，提出一种基于图匹配的分层布局算法（ Graph Matching Hierarchy，GMH）。基于图匹配思想对大图进行递归化简，然后应用FR算法对最粗化图进行布局，最后利用质心布局算法对图进行扩展。实验结果表明，GMH算法能够提高可视化效率，改善布局效果，且分层布局的结果更易于理解。