An experimental comparison of four graph drawing algorithms

被引:94
作者
DiBattista, G
Garg, A
Liotta, G
Tamassia, R
Tassinari, E
Vargiu, F
机构
[1] BROWN UNIV,DEPT COMP SCI,PROVIDENCE,RI 02912
[2] UNIV ROMA LA SAPIENZA,DIPARTIMENTO INFORMAT & SISTEMIST,I-00198 ROME,ITALY
[3] UNIV ROMA 3,DIP INFORMAT & AUTOMAZ,I-00146 ROME,ITALY
来源
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS | 1997年 / 7卷 / 5-6期
基金
美国国家科学基金会;
关键词
graph drawing; orthogonal drawings; algorithms implementation; experimental comparison of algorithms;
D O I
10.1016/S0925-7721(96)00005-3
中图分类号
O29 [应用数学];
学科分类号
070104 [应用数学];
摘要
In this paper we present an extensive experimental study comparing four general-purpose graph drawing algorithms. The four algorithms take as input general graphs (with no restrictions whatsoever on connectivity, planarity, etc.) and construct orthogonal grid drawings, which are widely used in software and database visualization applications, The test data (available by anonymous ftp) are 11,582 graphs, ranging from 10 to 100 vertices, which have been generated from a core set of 112 graphs used in ''real-life'' software engineering and database applications. The experiments provide a detailed quantitative evaluation of the performance of the four algorithms, and show that they exhibit trade-offs between ''aesthetic'' properties (e.g., crossings, bends, edge length) and running time. (C) 1997 Elsevier Science B.V.
引用
收藏
页码:303 / 325
页数:23
相关论文
共 50 条
[1]
A LAYOUT ALGORITHM FOR DATA FLOW DIAGRAMS [J].
BATINI, C ;
NARDELLI, E ;
TAMASSIA, R .
IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, 1986, 12 (04) :538-546
[2]
Batini C., 1992, CONCEPTUAL DATABASE
[3]
BATINI C, 1985, P 4 INT C ENT REL AP
[4]
PARAMETRIC GRAPH DRAWING [J].
BERTOLAZZI, P ;
DIBATTISTA, G ;
LIOTTA, G .
IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, 1995, 21 (08) :662-673
[5]
Brandenburg FJ, 1996, LECT NOTES COMPUT SC, V1027, P76, DOI 10.1007/BFb0021792
[6]
CHIBA N, 1985, ACTA INFORM, V22, P187, DOI 10.1007/BF00264230
[7]
A LINEAR-TIME ALGORITHM FOR DRAWING A PLANAR GRAPH ON A GRID [J].
CHROBAK, M ;
PAYNE, TH .
INFORMATION PROCESSING LETTERS, 1995, 54 (04) :241-246
[8]
COHEN RF, 1995, LECT NOTES COMPUTER, V894, P1
[9]
DAVIDSON R, 1989, DRAWING GRAPHS NICEL
[10]
Di Battista G., 1990, Proceedings of the 1990 IEEE Workshop on Visual Languages (Cat. No.90TH0330-1), P60, DOI 10.1109/WVL.1990.128383