Institution: | a Dip. Informatica e Automazione, Università di Roma Tre, via della Vasca Navale 84, 00146, Roma, Italy b Department of Computer Science, Brown University, 115 Waterman Street, Providence, RI 02912-1910, USA c Dip. Informatica e Sistemistica, Università di Roma “La Sapienza”, Via Salaria, 113 00198, Roma, Italy |
Abstract: | 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. |