Abstract
We report on our experiments with five graph drawing algorithms for general undirected graphs. These are the algorithms FR introduced by Fruchterman and Reingold [5], KK by Kamada and Kawai [11], DH by Davidson and Harel [1], Tu by Tunkelang [13] and GEM by Frick, Ludwig and Mehldau [6]. Implementations of these algorithms have been integrated into our GraphEd system [9]. We have tested these algorithms on a wide collection of examples and with different settings of parameters. Our examples are from original papers and by our own. The obtained drawings are evaluated both empirically and by GraphEd's evaluation toolkit. As a conclusion we can confirm the reported good behaviour of the algorithms. Combining time and quality we recommend to use GEM or KK first, then FR and Tu and finally DH.
This research is partially supported by the Deutsche Forschungsgemeinschaft, Grant Br 835/6-1, Forschungsschwerpunkt ”effiziente Algorithmen für diskrete Probleme und ihre Anwendungen”
Chapter PDF
References
Davidson, R., Harel, D.: Drawing graphs nicely using simulated annealing. Department of Applied Mathematics and Computer Science (1991)
Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Algorithms for drawing graphs: an annotated bibliography. Comput. Geom. Theory Appl. 4 (1991) 235–282
Di Battista, G., Garg, A., Liotta, G., Tassinari, E., Tamassia, R., Vargiu, F.: An experimental comparison of three graph drawing algorithms. Proc. 11th AMC Sympos. Comput. Geom. (1995)
Eades, P.: A heuristic for graph drawing. Congressus Numeratium 42 (1984) 149–160
Fruchtermann, T.M.J., Reingold, E.M.: Graph drawing by force-directed placement. Software, Practice and Experience 21 (1991) 1129–1164
Frick, A., Ludwig, A., Mehldau, H.: A fast adaptive layout algorithm for undirected graphs. Proc. Workshop on Graph Drawing 94. LNCS 894 (1994) 389–403
Harel, D., Sardas, M.: Randomized graph drawing with heavy-duty preprocessing. Department of Applied Mathematics and Computer Science Weizmann Institute of Science, Rehovot/Israel, Technical Report CS93-16 (1993)
Himsolt, M.: Konzeption und Implementierung von Grapheneditoren. Dissertation, Universität Passau, Shaker Verlag Aachen (1993)
Himsolt, M.: GraphEd: A graphical platform for the implementation of graph algorithms. Proc. Workshop on Graph Drawing 94, LNCS 894 (1994) 182–193
Himsolt, M.: Comparing and evaluating layout algorithms within GraphEd. J. Visual Languages and Computing 6 (1995)
Kamada, T., Kawai, S.: An algorithm for drawing general undirected graphs. Inf. Proc. Letters 31 (1989) 7–15
Rohrer, C.: Layout von Graphen unter besonderer Berücksichtigung von probabilistischen Algorithmen. Diplomarbeit, Universität Passau (1995)
Tunkelang, D.: A practical approach to drawing undirected graphs. Carnegie Mellon University (1994)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1996 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Brandenburg, F.J., Himsolt, M., Rohrer, C. (1996). An experimental comparison of force-directed and randomized graph drawing algorithms. In: Brandenburg, F.J. (eds) Graph Drawing. GD 1995. Lecture Notes in Computer Science, vol 1027. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0021792
Download citation
DOI: https://doi.org/10.1007/BFb0021792
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-60723-6
Online ISBN: 978-3-540-49351-8
eBook Packages: Springer Book Archive