language: en

An Experimental Comparison of Three Graph Drawing Algorithms

(Extended Abstract)

Giuseppe Di Battista
dibattista@iasi.rm.cnr.it
Roberto Tamassia
rt@cs.brown.edu
D. I. F. A. Univ. della Basilicata
85100 Potenza Italy
Ashim Garg
ag@cs.brown.edu
Emanuele Tassinari x
tassinar@dis.uniroma1.it
Dept. of Computer Science Brown University
Providence, RI 02912-1910 USA
Giuseppe Liotta
liotta@dis.uniroma1.it
Francesco Vargiu
vargiu@dis.uniroma1.it
Dip. Informatica e Sistemistica Univ. di Roma "La Sapienza"
00198 Roma Italy

Abstract In this paper we present an extensive experimental study comparing three general-purpose graph drawing algorithms. The three algorithms take as input general graphs (with no restrictions whatsoever on the 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 three algorithms, and show that they exhibit trade-offs between "aesthetic" properties (e.g., crossings, bends, edge length) and running time. The observed practical behavior of the algorithms is consistent with their theoretical properties. Research supported in part by the US National Science Foundation, by the US Army Research Office, by the US Office of Naval Research and the Advanced Research Projects Agency, by the NATO Scientific Affairs Division, by the "Progetto Finalizzato Sistemi Informatici e Calcolo Parallelo (Sottoprogetto 6, Infokit)" and Grant 94.23.CT07 of the Italian National Research Council (CNR), and by the ESPRIT II Basic Research Actions Program of the European Community (project ALgorithms and Complexity).

1 Introduction