Algorithmen zum automatischen Zeichnen von Graphen

Brandenburg, Franz J. and Jünger, Michael and Mutzel, Petra (1997) Algorithmen zum automatischen Zeichnen von Graphen. [Preprint]

[img] Other
128Kb

Abstract

Graph drawing is a new and growing area in Computer Science. It is concerned with the design, analysis, implementation and evaluation of new algorithms for aesthetically nice drawings of graphs. Through the use of some selected examples of applications, typical problems, and solutions, we would like to provide an introduction into this still relatively unknown field. And we survey activities and goals of a working group consisting of members of the universities of Halle, Köln and Passau and the Max-Planck-Institut für Informatik in Saarbrücken, that is funded by the German Science Foundation DFG under the program Èfficient Algorithms for Discrete Problems and their Applications'.

Item Type:Preprint
Additional Information:This article was published in August 1997 by Springer in the journal "Informatik-Spektrum", volume 20, pages 199-207. DOI: http://dx.doi.org/10.1007/s002870050066
Classifications:A General Literature > A.001 Introductory and Survey
ID Code:21
Alternative Locations:http://e-archive.informatik.uni-koeln.de/264/

Repository Staff Only: item control page

References

Beck, H. K. B. and Galil, H. -P. and Henkel, R. and Sedlmayr, E. (1992) Chemistry in circumstellar shells, I. chromospheric radiation fields and dust formation in optically thin shells of M-giants. Astron. Astrophys., 265 626-642.

Booth, K. and Lueker, G. (1976) Testing for consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. Comput. System Sci., 13 335-379.

Brandenburg, F. J. (1990) Nice drawings of graphs are computationally hard. LNCS, 439 1-15.

Brandenburg, F. J. (1996) On drawing planar angle graphs. MIP Bericht, Universität Passau.

Brandenburg, F. J. and Himsolt, M. and Rohrer, C. (1996) An experimental comparison on force-directed and randomized graph drawing algorithms. Proc. Graph Drawing 95, LNCS, 1027 76-87.

Brandenburg, F. J. (ed.) (1996) Proceedings Graph Drawing 95. LNCS, 1027.

Chai, J. and Han, X. and Tarjan, R. E. (1993) An O(mlogn)-time algorithm for the maximal planar subgraph problem. SIAM J. of Comput., 22 1142-1162.

Chiba, N. and Nishizeki, T. and Abe, S. and Ozawa, T. (1985) A linear algorithm for embedding planar graphs using PQ-trees. Journal of Computer and System Sciences, 30 54-76.

Chiba, N. and Onoguchi, K. and Nishizeki, T. (1985) Drawing planar graphs nicely. Acta Informatica, 22 187-201.

Chrobak, M. and Kant, G. (1993) Convex grid drawings of 3-connected planar graphs. Technical Report RUU-CS-93-45, Dept. of Comp. Sci., Untrecht University.

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

De Simone, C. and Jünger, M. (1996) On the two-connected planar spanning subgraph polytope. Technical Report No. 96.229, Institut für Informatik, Universität zu Köln, erscheint in Discrete Applied Mathematics.

Di Battista, G. and Eades, P. and Tamassia, R. and Tollis, I. G. (1994) Algorithms for drawing graphs: an annotated bibliography. Comput. Geometry: Theory Appl., 4 235-282.

Eades, P. (1984) A heuristic for graph drawing. Congressus Numerantium, 42 149-160.

Eades, P. and Wormland, N. C. (1994) Edge crossings in drawings of bipartite graphs. Algorithmica, 10 379-403.

Grötschel, M. and Jünger, M. and Reinelt, G. (1984) A cutting for plane algorithm for the linear ordering problem. Operations Research, 32 1195-1220.

Heine, H. (1995) Das Zeichnen planarer Graphen mit hoher Winkelauflösung. Diplomarbeit, Universität Passau.

Himsolt, M. (1993) Konzeption und Implementierung von Grapheneditoren. Shaker Verlag, Aachen.

Himsolt, M. (1996) A graph file format. Manuskript, Universität Passau.

Hopcroft, J. and Tarjan, R. E. (1974) Efficient planarity testing. J. Assoc. Comput. Mach., 21 549-568.

Jayakumar, R. and Thulasiraman, K. and Swamy, M. N. S. (1989) On O(n²)algorithms for graph planarization. IEEE Transactions on Computer-Aided Design, 8 (3) 257-267.

Jünger, M. and Mutzel, P. (1993) Solving the maximum planar subgraph problem by branch and cut. In: L.A. Wolsey and G. Rinaldi (ed.), Proc. 3rd IPCO Conference, Erice, pp. 479-492.

Jünger, M. and Mutzel, P. (1995) The polyhedral approach to the maximum planar subgraph problem: New chances for related problems. Proc. Graph Drawing 94, LNCS, 894 119-130.

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

Jünger, M. and Mutzel, P. (1996) Exact and heuristic algorithms for 2-layer straightline crossing minimization. Proc. Graph Drawing 95, LNCS, 1027 33-59. Revidierte Version erscheint in J. Graph Algorithms and Applications.

Jünger, M. and Thienel, S. (1997) The design of the branch and cut system ABACUS. Technical Report No. 97.260, Institut für Informatik, Universität zu Köln.

Kant, G. (1992) Drawing planar graphs using the Imcordering. Proc. 33rd Symp. on Found. of Comp. Sci., 101-110.

Kuratowski, K. (1930) Sur le problème des courbes gauches en topologie. Fund. Math., 15 271-283.

Lauer, H.(1995) Grapheneditoren: eine Wunschliste. Bericht WSI-95-4, Univ. Tübingen.

Leipert, S. (1996) The Tree Interface-Version 1.0 User Manual. Technical Report No. 96.242, Institut für Informatik, Universität zu Köln.

Mehlhorn, K. and Mutzel, P. (1996) On the embedding phase of the Hopcroft and Tarjan planarity testing algorithm. Algorithmica, 16 233-242.

Mehlhorn, K. and Mutzel, P. and Näher, S. (1993) An implementation of the Hopcroft and Tarjan planarity test and embedding algorithm. Technical Report MPI-I-93-151, Max-Planck-Institut für Informatik, Saarbrücken.

Mehlhorn, K. and Näher, S. (1995) LEDA: A platform for combinatorial and geometric computing. Comm. Assoc. Comput. Mach., 38 96-102.

Mutzel, P. (1994) The maximum planar subgraph problem. Dissertation, Universität zu Köln.

Mutzel, P. (1995) A polyhedral approach to planar augmentation and related problems. Proc. ESA 95, LNCS, 979 494-507.

Mutzel, P. (1996) An alternative approach for drawing hierarchical graphs. Proc. Graph Drawing 96, LNCS, erscheint 1997.

North, S. (ed.) (1996) Proceedings Graph Drawing 96, LNCS, erscheint 1997.

Purchase, H. C. and Cohen, R. F. and James, M. (1996) Validating graph drawing aesthetics. Proc. Graph Drawing 95, LNCS, 1027 435-446.

Reingold, Edward M. and Tilford, John S. (1981) Tidier drawings of trees. IEEE Transactions on Software Engineering, 7 (2) 223-228.

Schnyder, W. (1990) Embedding planar graphs on the grid. Proc. 1st ACM-SIAM Symp. on Discrete Algorithms, 138-147.

Stoer, M. (1992) Design of Survivable Networks. Lecture Notes in Mathematics, Springer-Verlag, Berlin.

Sugiyama, K. and Tagawa, S. and Toda, M. (1981) Methods for visual understanding of hierarchical system structures. IEEE Transactions on Systems, Man, and Cybernetics, 11 109-125.

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

Tamassia, R. and Tollis, I. G. (eds.) (1995) Proceedings Graph Drawing 94, LNCS, 894.

Thienel, S. (1995) ABACUS - A Branch And CUt System. Dissertation, Universität zu Köln.

Tutte, W. T. (1963) How to draw a graph. Proc. London Math. Soc., 13 743-768.

Wagner, K. (1936) Bemerkungen zum Vierfarbenproblem. Jahresbericht Deutsch. Math., 46 26-32.

Walker, J. Q. II (1990) A node-positioning algorithm for general trees. Software - Practice and Experience, 20 685-705.

Woods, D. R. (1981) Drawing planar graphs. Technical Report STAN-CS-82-943, Computer Science Dept., Stanford University.