A Fast Heuristic for Hierarchical Manhattan Layout

Sander, Georg (1996) A Fast Heuristic for Hierarchical Manhattan Layout. In: Symposium on Graph Drawing, GD 1995, September 20-22, 1995, Passau, Germany , pp. 447-458 (Official URL: http://dx.doi.org/10.1007/BFb0021828).

Full text not available from this repository.

Abstract

A fast heuristic for the layout of directed graphs according to Manhattan convention is presented. Nodes are placed into layers. Edges consist of sequences of vertical and horizontal segments. Sharing of segments is allowed in certain situations. The algorithm is an extension of the hierarchical layout method [11, 15] that includes crossing reduction and emphasis on a uniform edge orientation. Compared to the original algorithm, the time overhead is O(n+ek) where n, e and k are the number of nodes, of edges, and the maximal number of line rows between two layers of nodes. It produces drawings where each edge has at most four bends.

Item Type:Conference Paper
Additional Information:10.1007/BFb0021828
Classifications:G Algorithms and Complexity > G.420 Crossings
G Algorithms and Complexity > G.210 Bends
P Styles > P.480 Layered
ID Code:211

Repository Staff Only: item control page

References

Baker, B. S.; Bhatt, S. N.; Leighton, F. T.: An Approximation Algorithm for Manhattan Routing, in Preparata, F. P., ed.: Advances in Computing Research, Vol. 2, pp. 205-229, JAI Press, Greenwich, Connecticut, 1984.

Batini, C.; Nardelli, E.; Tamassia, R.: A Layout Algorithm for Data Flow Diagrams, IEEE Trans. on Software Engineering, SE-12(4), pp. 538-546, 1986.

Bhatt, S. N.; Cosmadakis, S.S.: The Complexity of Minimizing Wire Lengths in VLSI Layouts, Information Processing Letters, 25, pp. 263-267, 1987.

Biedl, T.; Kant, G.: A Better Heuristic for Orthogonal Graph Drawings, Technical Report UU-CS-1995-04, Utrecht University, 1995, also in Proc. 2nd Ann. European Symposium on Algorithms (ESA '94), LNCS 855, pp. 24-35, Springer-Verlag, 1994.

Even, S.; Granot, G.: Grid Layouts of Block Diagrams - Bounding the Number of Bends in Each Connection, in Tamassia, R.; Tollis, I. G., eds.: Graph Drawing, Proc. DIMACS Intern. Workshop GD '94, LNCS 894, pp. 64-75, Springer-Verlag, 1995.

Gansner, E. R.; Koutsofios, E.; North, S. C.; Vo, K.-P.: A Technique for Drawing Directed Graphs, IEEE Trans. on Software Engineering, 19(3), pp. 214-230, 1993.

Himsolt, M.: GraphEd - A Graphical Platform for the Implementation of Graph Algorithms, in Tamassia, R.; Tollis, I.G., eds.: Graph Drawing, Proc. DIMACS Intern. Workshop GD '94, LNCS 894, pp. 182-193, Springer-Verlag, 1995.

Johnson, D.: The NP-completeness column: An ongoing guide, Journal on Algorithms, 3(1), pp. 215-218, 1982.

Protsko, L. B.; Sorenson, P. G.; Tremblay, J. P.; Schaefer, D. A. : Towards the Automatic Generation of Software Diagrams, IEEE Trans. on Software Engineering, 17(1), pp. 10-21, 1991.

Sander, G.: Graph Layout Through the VCG Tool, in Tamassia, R.; Tollis, I. G., eds.: Graph Drawing, Proc. DIMACS Intern. Workshop GD '94, LNCS 894, pp. 194-205, Springer-Verlag, 1995. The VCG tool is publicly available via http://www.cs.uni-sb.de:80/RW/users/sander/html/gsvcg1.html.

Sugiyama, K., Tagawa, S., Toda, M.: Methods for Visual Understanding of Hierarchical Systems, IEEE Trans. Sys., Man, and Cybernetics, SMC 11(2), pp. 109-125, 1981.

Tamassia, R.: On Embedding a Graph in the Grid with the Minimum Number of Bends, SIAM Journal of Computing, 16(3), pp. 421-444, 1987.

Tamassia, R., Tollis, I. G.: Planar Grid Embedding in Linear Time, IEEE Trans. on Circuits and Systems, 36(9), pp. 1230-1234, 1989.

Vijayan G., Wigderson A.: Rectilinear Graphs and Their Embeddings, SIAM Journal of Computing, 14(2), pp. 355-372, 1985.

Warfield, N. J.: Crossing Theory and Hierarchy Mapping, IEEE Trans. Sys., Man, and Cybernetics, SMC 7(7), pp. 505-523, 1977.

Wieners-Lummer, C.: Manhattan Channel Routing with Good Theoretical and Practical Performance, ACM SIAM Symp. on Disc. Alg., pp. 465-474, 1990.