• 中国计算机学会会刊
  • 中国科技核心期刊
  • 中文核心期刊
论文

无向关系图视觉清晰化显示算法

展开
  • (温州大学物理与电子信息工程学院,浙江 温州 325035)
方文其(1990),男,浙江苍南人,研究方向为计算机图形学和人工智能。胡明晓(1965),男,浙江永嘉人,硕士,讲师,研究方向为计算机图形学和人工智能。

收稿日期: 2010-09-03

  修回日期: 2010-12-28

  网络出版日期: 2011-06-25

基金资助

浙江省新苗人才计划资助项目(团浙联〔2010〕15号);温州市科技局资助项目(H20090049)

A Visually Clarifying Display Algorithm for Undirected Relation Graphs

Expand
  • (School of Physics and Electronic Information Engineering,Wenzhou University,Wenzhou 325035,China)

Received date: 2010-09-03

  Revised date: 2010-12-28

  Online published: 2011-06-25

摘要

本文提出了一种无向图视觉清晰化显示算法,使一般的无向关系图经过该算法重新确定顶点位置后,能得到清晰美观的输出结果。该算法首先将无向关系图去除孤立点,分离连通分支,并通过识别割边将每个连通分支分解成一系列的团,每个团内无割边,这些团以树型结构连接;然后通过识别割点和虚连线将每个团分解成子团,每个子团内无割点;最后将子团内顶点均匀分布在一个圆环上。该算法的优点在于实现方便,方法简单,运行高效,输出结果美观,并易于并行化。

本文引用格式

方文其,胡明晓 . 无向关系图视觉清晰化显示算法[J]. 计算机工程与科学, 2011 , 33(6) : 51 -56 . DOI: 10.3969/j.issn.1007130X.2011.

Abstract

A visually clarifying display algorithm for undirected relation graphs is proposed in this paper. Given an ordinary undirected relation graph, after it is processed by the novel algorithm determining the new positions of the vertices, it becomes more clear in aesthetic criteria. First, for a given graph, any isolated vertices are deleted, all the connected branches are decomposed. For each connected branch, it is decomposed into several cliques linked as a tree via recognizing the cut edges (bridges). Then the cliques are decomposed into several subcliques via recognizing the cut vertices. Finally, the vertices in the subclique are uniformly located in a circle. The algorithm is featured with convenient implementation, simple model, fast processing, clear output results and easy parallelization.

参考文献

[1]Eades P. A Heuristic for Graph Drawing[J]. Congressus Numerantium,1984(42):149160.
[2]Ron D, David H. Drawing Graphs Nicely Using Simulated Annealing[J]. ACM Transactions on Graphics,1996,15(4):301331.
[3]黄竞伟,康立山,陈毓屏.一个新的无向图画图算法[J].软件学报,2000,11(1):138142.
[4]Charis P,Constantinos V. Drawing Graphs Using Modular Decomposition[C]∥Proc of the 13th Int’l Symp on Graph Drawing, 2005:343354.
[5]张清国,叶俊民,张维,等.用遗传算法画无向图[J].计算机工程与科学,2006,28(6):5861.
[6]张磊,孙松,李经通,等.网络拓扑图形化显示方法及装置[P].发明专利200910011924.0, 2009.
[7]Hong SeokHee,Hiroshi N. An Algorithm for Constructing StarShaped Drawings of Plane Graphs[J]. Computational Geometry, 2010(43):191206.

文章导航

/