AN ALGORITHM FOR DRAWING GENERAL UNDIRECTED GRAPHS
AN ALGORITHM FOR DRAWING GENERAL UNDIRECTED GRAPHS
复制标题
DOI：
10.1016/0020-0190(89)90102-6
复制
发表时间：
1989-04-12
影响因子：
0.5
通讯作者：
KAWAI, S
中科院分区：
文献类型：
--
作者：
KAMADA, T;KAWAI, S
图（网络）是在计算机中处理的非常常见的数据结构。在许多信息系统中，图被广泛用于可视化地表示图结构。为了自动绘制例如状态图、数据流图、Petri网和实体关系图的图，需要基本的图绘制算法。自动绘图的最新技术在[7，19]中进行了全面的调查。一般无向图的算法很少。本文提出了一种简单而成功的无向图和赋权图的绘制算法。我们的算法的基本思想如下。我们把图中两个顶点之间理想的”几何”（欧几里德）距离看作是它们在相应图中的”图论”距离。我们介绍了一个虚拟的动态系统，其中每两个顶点连接的“弹簧”的这种理想的长度。然后，我们把顶点的最优布局看作是系统总弹簧能量最小的状态。文[6]中引入了画一般图的”弹簧”思想，并用类似的方法画有固定边界的平面图[2，20]。本文在弹簧模型的基础上，给出了一个新的有意义的图形绘制结果。
Graphs (networks) are very common data structures which are handled in computers. Diagrams are widely used to represent the graph structures visually in many information systems. In order to automatically draw the diagrams which are, for example, state graphs, data-flow graphs, Petri nets, and entity-relationship diagrams, basic graph drawing algorithms are required. The state of the art in automatic drawing is surveyed comprehensively in [7, 19]. There have been only a few algorithms for general undirected graphs. This paper presents a simple but successful algorithm for drawing undirected graphs and weighted graphs. The basic idea of our algorithm is as follows. We regard the desirable" geometric"(Euclidean) distance between two vertices in the drawing as the" graph theoretic" distance between them in the corresponding graph. We introduce a virtual dynamic system in which every two vertices are connected by a" spring" of such desirable length. Then, we regard the optimal layout of vertices as the state in which the total spring energy of the system is minimal. The" spring" idea for drawing general graphs was introduced in [6], and similar methods were used for drawing planar graphs with fixed boundary [2, 20]. This paper brings a new significant result in graph drawing based on the spring model.