摘要
本文提出了一种无向图视觉清晰化显示算法,使一般的无向关系图经过该算法重新确定顶点位置后,能得到清晰美观的输出结果。该算法首先将无向关系图去除孤立点,分离连通分支,并通过识别割边将每个连通分支分解成一系列的团,每个团内无割边,这些团以树型结构连接;然后通过识别割点和虚连线将每个团分解成子团,每个子团内无割点;最后将子团内顶点均匀分布在一个圆环上。该算法的优点在于实现方便,方法简单,运行高效,输出结果美观,并易于并行化。
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.
出处
《计算机工程与科学》
CSCD
北大核心
2011年第6期51-56,共6页
Computer Engineering & Science
基金
浙江省新苗人才计划资助项目(团浙联〔2010〕15号)
温州市科技局资助项目(H20090049)
关键词
无向图
清晰化显示
割边
割点
团
undirected graph
clarifying display
cut edge
cut vertex
clique
