A Hierarchical Layout Algorithm Based on Graph Matching

doi:10.3969/j.issn.1006-2475.2015.08.022

Abstract

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

Key words: visualization, undirected graph, graph matching, mass-center prolong, hierarchical layout

CLC Number:

TP393

ZHAO Yu-cong, ZHONG Zhi-nong, WU Ye, JING Ning. A Hierarchical Layout Algorithm Based on Graph Matching[J]. Computer and Modernization, doi: 10.3969/j.issn.1006-2475.2015.08.022.

References

［1］杨彦波,刘滨,祁明月,等. 信息可视化研究综述［J］. 河北科技大学学报, 2014,35(1):91-102.
［2］黄竞伟,康立山,陈毓屏. 一个新的无向图画图算法［J］. 软件学报， 2000,11(1):138-142.
［3］黄竞伟. 基于遗传算法的画图算法研究［D］. 武汉:武汉大学, 2001.
［4］ Koren Y, Carmel L, Harel D. Drawing huge graphs by algebraic multigrid optimization［J］. Multiscale Modeling and Simulation, 2003,1(4):645-673.
［5］〖JP2〗Harel D, Koren Y. Graph drawing by high-dimensional embedding［J］. Journal of Graph Algorithms and Application, 2004,8(2):195-214.
［6］〖JP2〗Eades P. A heuristic for graph drawing［J］. Congresses Numerantium, 1984,42:149-160.
［7］ Kamada T, Kawai S. An algorithm for drawing general undirected graphs［J］. Information Processing Letters, 1989,31(1):7-15.
［8］ Davidson R, Harel D. Drawing graphs nicely using simulated annealing［J］. ACM Transactions on Graphics(TOG), 1996,15(4):301-331.
［9］ Fruchterman T M J, Reingold E M. Graph drawing by force-directed placement［J］. Software-Practice and Experience, 1991,21(11):1129-1164.
［10］Davis L. Genetic algorithms and simulated annealing［M］. Morgan Kaufmann Publishers Inc., 1987.
［11］Rodrigues J F, Tong Hanghang, Pan Jiayu, et al. Large graph analysis in the GMine system［J］. IEEE Transactions on Knowledge & Data Engineering, 2013,25(1):106-118.
［12］Hadany R, Harel D. A multi-scale algorithm for drawing graphs nicely［J］. Discrete Applied Mathematics, 2001,113(1):3-21.
［13］Harel D, Koren Y. A fast multi-scale method for drawing large graphs［J］. Journal of Graph Algorithms and Applications, 2002,6(3):179-202.
［14］Walshaw C. A multilevel algorithm for force-directed graph drawing［J］. Journal of Graph Algorithms and Applications, 2003,7(3):253-285.
［15］Gajer P, Goodrich M T, Kobourov S G. A fast multi-dimensional algorithm for drawing large graphs［J］. Computational Geometry: Theory and Applications, 2004,29(1):3-18.［16］Hu Yifan, Scott J A. A multilevel algorithm for wavefront reduction［J］. SIAM Journal on Scientific Computing, 2001,23(4):1352-1375.
［17］Hu Yifan. Efficient and high quality force-directed graph drawing［J］. The Mathematica Journal, 2005,10(1):37-71.

[1]	LIU Cong, NIE Yun, WANG Guo-wei. Entity Multi-expression Method for 3D Simulation of Space [J]. Computer and Modernization, 2023, 0(04): 90-94.
[2]	TIAN Mao-chun, ZOU Xian-yong, YANG Yue, FAN Guang-wei, LAI Hang. 3D Dynamic Visualization Design and Simulation of Wind Field on Web [J]. Computer and Modernization, 2022, 0(04): 97-102.
[3]	LIU Jia-xin, YOU Zhen, HUANG Jie-wen, CHEN Jia-xiang, HU Hong-wen, . Graph Algorithm Virtual Simulation System Based on Lushan 3D Scene [J]. Computer and Modernization, 2020, 0(12): 90-98.
[4]	WANG Xiao-yu, SUN Ka. Visualization of 3D Virtual Campus Based on osgEarth [J]. Computer and Modernization, 2020, 0(11): 89-93.
[5]	WU Zhong-de, LUO Xiao-fang, HOU Zeng-xuan, DUAN Peng-xuan, LI Nan-nan. Visualization of Radar Detection Range Based on 3D Earth Scene Under Interference Condition [J]. Computer and Modernization, 2020, 0(10): 90-96.
[6]	ZHANG Cheng, MIAO Xin-rui, MOU Xue-man. 3D Visualization of High Precision Map Lanes [J]. Computer and Modernization, 2020, 0(08): 21-25.
[7]	WANGYong-sheng1,2，LIHui1,2，CHENMei1,2，DAIZhen-yu1,2，ZHUMing3. VISDMiner:AnInteractiveDataMiningProcessVisualizationSystem [J]. Computer and Modernization, 2018, 0(06): 72-.
[8]	CAO Zhong, LI Fu-chen, YANG Hao-fei. Urban Traffic Flows Analysis and Visualization Based on Mobile Phone Signaling Data [J]. Computer and Modernization, 2018, 0(03): 116-.
[9]	LI Jia-qi， ZHENG Hao. A Heterogeneous Mixed Fast Drawing Framework Based on Vec-map Data [J]. Computer and Modernization, 2018, 0(01): 56-61.
[10]	LIU Ge1， LIU Yun-fei2. Visualization and Visual Analysis System of Environmental Quality Data [J]. Computer and Modernization, 2018, 0(01): 62-68.
[11]	CHEN Guo-xin， HAO Xuan-wen， QIU Guo-yong， WU Zhen-qiang. Factor Analysis and Empirical Study on Effect of Learner’s Learning in Online Teaching [J]. Computer and Modernization, 2017, 0(9): 106-110.
[12]	DENG Xianyu1, GUO Daming2. Application of Information Visualization in Monitoring #br# and Optimization for Wireless Internet [J]. Computer and Modernization, 2017, 0(8): 71-.
[13]	DING Zhi-jun, ZHOU Ze-xia, WEI Zhi-hua. An Auxiliary Teaching Software About Process Visualization Class C Compiler [J]. Computer and Modernization, 2017, 0(6): 34-39.
[14]	WANG Li1, LIU Xiang2, LIN Enai2, DENG Gang2. A New Generation Intelligent Cloud Computing Data Center of #br# China’s Civil Aviation [J]. Computer and Modernization, 2016, 0(5): 111-115.
[15]	JIANG Bao-qing1,2, HAO Rui-peng1,2. A Population Data Visualization Monitoring System Based on LBS [J]. Computer and Modernization, 2016, 251(07): 107-110,114.