Layout of Directed Hypergraphs with Orthogonal Hyperedges

Sander, Georg (2003) Layout of Directed Hypergraphs with Orthogonal Hyperedges. [Departmental Technical Report] (Unpublished)

This is the latest version of this item.

[img] Postscript - Requires a viewer, such as GSview
10Mb

Abstract

We present a layout algorithm for directed hypergraphs. A hypergraph contains hyperedges that have multiple source and target nodes. The hyperedges are drawn with orthogonal segments. The nodes are organized in layers, so that for the majority of hyperedges the source nodes are placed in a higher layer than the target nodes, similar to traditional hierarchical layout [10, 13]. The algorithm was implemented using ILOG JViews [12] for a project that targeted electrical signal visualization.

Item Type:Departmental Technical Report
Additional Information:This is the long (full) version of paper ID 467. The shorter version (extended abstract) was published on GD 2003 with Springer and is in the data base under ID 467.
Keywords:hypergraph, orthogonal, Sugyama layout, electrical diagram
Classifications:P Styles > P.420 Hyper
M Methods > M.500 Layered
P Styles > P.600 Poly-line > P.600.700 Orthogonal
ID Code:585
Alternative Locations:ftp://ftp.ilog.fr/private/ILOG.de/rnd/gsander/public/hypergraph.ps.gz

Available Versions of this Item

Repository Staff Only: item control page

References

Di Battista, G. and Eades, P. and Tamassia, R. and Tollis, I. G., Graph Drawing, Prentice-Hall, Inc., New Jersey, 1999

Johnson, D. S. and Pollak, H.O., Hypergraph planarity and the complexity of drawing venn diagrams, Journal of Graph Theory, 11(3): 309-325, 1987

Sander, G., Graph layout through the VCG tool, In Proc. DIMACS International Workshop on Graph Drawing, GD'94, Springer, LNCS 894, 1995, pages 194-205

Sander, G., A fast heuristic for hierarchical Manhattan layout, In Proc. Symposium on Graph Drawing, GD'95, Springer, LNCS 1027, 1996, pages 447-458

Bertault, F. and Eades, P., Drawing Hypergraphs in the Subset Standard, In Proc. Symposium on Graph Drawing, GD 2000, Springer, LNCS 1984, 2001, pages 164-169

Gropp, H., The Drawing of Configurations, In Proc. Symposium on Graph Drawing, GD'95, Springer, LNCS 1027, 1996, pages 267-276

Garey, M. R. and Johnson, D. S., Computers and intractability: A guide through the theory of NP-Completeness, W. H. Freeman, New York, NY, 1979,

Klemetti, H. and Lapinleimu, I. and Mäkinen, E. and Sieranta, M., A programming project: Trimming the spring algorithm for drawing hypergraphs, SIGCSE Bulletin, 1995, 27(3), 34-38

Di Battista, G. and Tamassia, R., Algorithms for Plane Representations of Acyclic Digraphs, Theoret. Comput. Sci., 1988, 61, 175-198

Mäkinen, E., How to draw a hypergraph, International Journal of Computer Mathematics, 1990, 34, 177-185

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

Sander, G. and Vasiliu, A., The ILOG JViews graph layout module, In Proc. Symposium on Graph Drawing, GD 2001, Springer, LNCS 2265, 2002, pages 438--439

Eschbach, T. and Günther, W. and Becker, B.Crossing Reduction for Orthogonal Circuit Visualization, In Proc. International Conference on VLSI, Las Vegas, CSREA Press, 2003, pages 107-113