Graph Drawing Algorithm Engineering with AGD

Gutwenger, Carsten and Jünger, Michael and Klau, Gunnar W. and Leipert, Sebastian and Mutzel, Petra (2000) Graph Drawing Algorithm Engineering with AGD. [Preprint]

Full text available as:

PDF - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
209Kb

Abstract

We discuss the algorithm engineering aspects of AGD, a software library of algorithms for graph drawing. AGD represents algorithms as classes that provide one or more methods for calling the algorithm. There is a common base class, also called the type of an algorithm, for algorithms providing basically the same functionality. This enables us to exchange components and experiment with various algorithms and implementations of the same type. We give examples for algorithm engineering with AGD for drawing general non-hierarchical graphs and hierarchical graphs.

Item Type:	Preprint
Classifications:	S Software and Systems > S.001 General
ID Code:	14
Deposited By:	GDEA, Administration
Deposited On:	17 Jul 2003
Last Modified:	18 Sep 2008 13:08
Alternative Locations:	http://www.zaik.uni-koeln.de/%7Epaper/preprints.html?show=zaik2000-394

Repository Staff Only: item control page

References

AGD User Manual (Version 1.2) (2000). Max-Planck-Institut Saarbrücken, Technische Universität Wien, Universität zu Köln, Universität Trier. See also http://www.mpi-sb.mpg.de/AGD/, to appear.

Batini, C. and Nardelli, E. and Tamassia, R (1986) A layout algorithm for data-flow diagrams. IEEE Trans. Soft. Eng., SE-12 (4) 538-546.

Batini, C. and Talamo, M. and Tamassia, R. (1984) Computer aided layout of entity relationship diagrams. The Journal of Systems and Software, 4 163-173.

Bridgeman, S and Di Battista, G. and Didimo, W. and Liotta, G. and Tamassia, R. and Vismara, L. (2000) Turn-regularity and optimal area drawings for orthogonal representations. Computational Geometry Theory and Applications (CGTA), to appear.

Buchheim, C. and Jünger, M. and Leipert, S. (1999) A fast layout algorithm for k-level graphs. Technical Report No. 99.368, Institut für Informatik, Universität zu Köln.

Chrobak, M. and Kant, G. (1997) Convex grid drawings of 3-connected planar graphs. Internat. Journal on Computational Geometry and Applications, 7 (3) 211-224.

Coffman, E. G. and Graham, R. L. (1972) Optimal scheduling for two processor systems. Acta Informatica, 1 200-213.

De Fraysseix, H. and Pach, J. and Pollack, R. (1990) How to draw a planar graph on a grid. Combinatorica, 10 (1) 41-51.

Di Battista, G. and Tamassia, R. (1996) On-line planarity testing. SIAM J. Comput.,25 (5) 956-997.

Di Battista, G. and Tamassia, R. and Tollis, I. G. (1992) Area requirement and symmetry display of planar upward drawings. Discrete Comput. Geom., 7 381-401.

Eades, P. and Kelly, D. (1986) Heuristics for reducing crossings in 2-layered networks. Ars Combinatoria, 21 (A) 89-98.

Eades, P. and Lin, X. (1995) A new heuristic for the feedback arc set problem. Australian Journal of Combinatorics, 12 15-26.

Eades, P. and Mutzel, P. (1999) Graph drawing algorithms. In: Atallah, M. (ed.) CRC Handbook of Algorithms and Theory of Computation, chapter 9, pages 9-1-9-26. CRC Press.

Eades, P. and Wormland, N. (1986) The median heuristic for drawing 2-layered networks. Technical Report 69, Department of Computer Science, University of Queensland.

Fialko, S. (1997) Das planare Augmentierungsproblem. Master s thesis, Universität des Saarlandes, Saarbrücken.

Fialko, S. and Mutzel, P. (1998) A new approximation algorithms for the planar augmentation problem. In: Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 98), San Francisco, California, ACM Press, pp. 260-269.

Fößmeyer, U. and Kaufmann, M. (1996) Drawing high degree graphs with low bend numbers. In: F. J. Brandenburg (ed.) Graph Drawing (Proc. GD 95), volume 1027 of LNCS, Springer, pp. 254-266.

Fruchterman, T. and Reingold, E. (1991) Graph drawing by force-directed placement. Softw. - Pract. Exp., 21 (11) 1129-1164.

Gansner, E. R. and Koutsofios, E. and North, S. C. and Vo, K. P. (1993) A technique for drawing directed graphs. IEEE Trans. Softw. Eng., 19 (3) 214-230.

Graph drawing toolkit: an object-oriented library for handling and drawing graphs. http://www.dia.uniroma3.it/gdt.

Gelfand, N. and Tamassia, R. (1998) Algorithmic patterns for orthogonal graph drawing. In: S. Whitesides (ed.) Graph Drawing (Proc. GD 98), volume 1547 of Lecture notes in Computer Science, Springer Verlag, pp. 138-152.

Grötschel. M and Jünger, M. and Reinelt, G. (1985) On the acyclic subgraph polytope. Mathematical Programming, 33 28-42.

Gutwenger, C. and P. Mutzel, P. (1997) Grid embedding of biconnected planar graphs. Extended Abstract, Max-Planck-Institut für Informatik, Saarbrücken, Germany.

Gutwenger, C. and Mutzel, P. (1998) Planar polyline drawings with good angular resolution. In: S. Whitesides (ed.) Graph Drawing (Proc. GD 98), volume 1547 of LNCS, Springer Verlag, pp. 167-182.

Gutwenger, C. and Mutzel, P. (2000) A linear-time implementation of SPQR-trees. Technical report, Technische Universität Wien.

Gutwenger, C. and Mutzel, P. and Weiskircher, R. (2000) Inserting an edge into a planar graph. Technical report, Technische Universität Wien, Submitted for publication.

Gutwenger, C. and Mutzel, P. and Ziegler, T. and Weiskircher, R. (2000) Experiments with combinatorial embeddings in graph drawing. Manuscript.

Himsolt, M. (1997) GML: A portable graph file format. Technical report, Universität Passau, see also http://www.uni-passau.de/Graphlet/GML.

Jünger, M. and Leipert, S. and Mutzel, P. (1998) A note on computing a maximal planar subgraph using PQ-trees. IEEE Transactions on Computer-Aided Design, 17 (7).

Jünger, M. and Mutzel, P. (1994) The polyhedral approach to the maximum planar subgraph problem: New Chances for related problems. In: DIMACS Graph Drawing 94, volume 894 of LNCS, Springer Verlag, pp. 119-130.

Jünger, M. and Mutzel, P. (1996) 2-layer straightline crossing minimization: Performance of exact and heuristic algorithms.Journal of Graph Algorithms and Applications (JGAA)(http://www.cs.brown.edu/publications/jgaa/), 1 (1) 1-25.

Jünger, M. and Mutzel, P. (1996) Maximum planar subgraphs and nice embeddings: Practical layout tools. Algorithmica, Special Issue on Graph Drawing, 16 (1) 33-59.

Jünger, M. and Thienel, S. (1998) Introduction to ABACUS - A Brunch-and-Cut System. Operations Research Letters, 22 83-95.

Jünger, M. and Thienel, S. (2000) The ABACKUS system for branch-and-cut and price algorithms in integer programming and combinatorial optimization. Software - Practice and Experience, to appear.

Kant, G. (1996) Drawing planar graphs using the canonical ordering. Algorithmica, Special Issue on Graph Drawing, 16 (1) 4-32.

Klau, G. W. and Klein, K. and Mutzel, P. (2000) An experimental comparison of orthogonal compaction algorithms. Technical report, Technische Universität Wien.

Klau, G. W. and Mutzel, P. (1998) Quasi-orthogonal drawing of planar graphs. Technical Report MPI-I-98-1-013, Max-Planck-Institut für Informatik, Saarbrücken.

Klau, G. W. and P. Mutzel, P. (1999) Optimal compaction of orthogonal grid drawings. In: G. P. Cornuéjols, R. E. Burkhard, and G. J. Woeginger, (ed.) Integer Programming and Combinatorial Optimization (IPCO 99), volume 1610 of LNCS, Springer, pp. 304-319.

Lengauer, T. (1990) Combinatorial Algorithms for Integrated Circuit Layout. John Wiley & Sons, New York.

Matuszewski, C. and Schönfeld, R. and Molitor, P. (1999) Using sifting for k-layer crossing mininization. In: J. Kratochvil (ed.) Graph Drawing (Proc. GD 99), volume 1731 of LNCS, Springer-Verlag, pp. 217-224.

Mehlhorm, K. and Näher, S. and Seel, M. and Uhrig, Ch. (2000) The LEDA User Manual (Version R 4.1). Max-Planck-Institut für Informatik, Saarbrücken, Germany. See also http://www.mpi-sb.mpg.de/LEDA/leda.html.

Mutzel, P. (1994) The maximum planar subgraph problem. PhD thesis, Institut für Informatik, Universität zu Köln.

Mutzel, P. (1995) A polyhedral approach to planar augmentation and related problems. In: Paul Spirakis (ed.) Annual European Symposium on Algorithms (ESA-3): Corfu, Greece, September 25-27, 1995;proceedings, volume 979 of LNCS, Berlin, Springer, pp. 494-507.

Mutzel, P. and Ziegler, T. (1999) The constrained crossing minimization problem. In: J. Kratochvil (ed.) Graph Drawing (Proc. GD 99), volume 1731 of Lecture Notes in Computer Science, Springer-Verlag, pp. 175-185.

Reingold, E. and Tilford, J. (1981) Tidier drawing of trees. IEEE Trans. Softw. Eng., SE-7 (2) 223-228.

Rosenstiehl, P. and Tarjan, R. E. (1986) Rectilinear planar layouts and bipolar orientations of planar graphs. Discrete Comput. Geom., 1 (4) 343-353.

Sugiyama, K. and Tagawa, S. and Toda, M. (1981) Methods for visual understanding of hierarchical systems. IEEE Trans. Syst. Man Cybern., SMC-11 (2) 109-125.

Tamassia, R. (1987) On embedding a graph in the grid with minimum number of bends. SIAM J. Comput., 16 (3) 421-444.

Tamassia, R. and Di Battista, G. and Batini, C. (1988) Automatic graph drawing and readability of diagrams. IEEE Trans. Syst. Man Cybern., SMC-18 (1) 61-79.

Tutte, W. T. (1963) How to draw a graph. Proceedings London Mathematical Society, 13 (3) 743-768.

Walker, J. Q. II (1990) A node-positioning algorithm for general trees. Softw. - Pract. Exp., 20 (7) 685-705.