Applying Crossing Reduction Strategies to Layered Compound Graphs

Forster, Michael (2002) Applying Crossing Reduction Strategies to Layered Compound Graphs. In: Graph Drawing 10th International Symposium, GD 2002, August 26-28, 2002, Irvine, CA, USA , pp. 276-284 (Official URL: http://dx.doi.org/10.1007/3-540-36151-0_26).

Full text not available from this repository.

Abstract

We present a new method for the application of 2-layer crossing reduction algorithms to layered compound graphs. It is based on an algorithm by Sander [7-9] and improves it with fewer crossings. Our method is optimal in the sense that it does not introduce unnecessary crossings by itself. If used with an optimal 2-layer crossing reduction algorithm, the crossing reduction for 2-layer compound graphs is optimal, too.

Item Type:Conference Paper
Additional Information:10.1007/3-540-36151-0_26
Classifications:M Methods > M.999 Others
G Algorithms and Complexity > G.999 Others
G Algorithms and Complexity > G.420 Crossings
P Styles > P.480 Layered
P Styles > P.240 Compound
ID Code:347

Repository Staff Only: item control page

References

Ralf Brockenauer and Sabine Cornelsen. Drawing clusters and hierarchies. In Kaufmann and Wagner [6], chapter 8, pages 193-227.

Giuseppe di Battista, Peter Eades, Roberto Tamassia, and Ioannis G. Tollis. Graph Drawing. Prentice Hall, 1999.

Peter Eades and Nicholas C. Wormland. Edge crossings in drawings of bipartite graphs. Algorithmica, 11:379-403, 1994.

Michael Jünger and Petra Mutzel. Exact and heuristic algorithms for 2-layer straightline crossing minimization. In Proc. Workshop on Graph Drawing '95, pages 337-348. Springer, 1996.

Michael Jünger and Petra Mutzel. 2-layer straightline crossing minimization: Performance of exact and heuristic algorithms. Journal of Graph Algorithms and Application, 1(1):1-25, 1997.

Michael Kaufmann and Dorothea Wagner, editors. Drawing Graphs, volume 2025 of Lecture Notes in Computer Science. Springer, 2001.

Georg Sander. Layout of compound directed graphs. Technical Report A/03/96, Universität Saarbrücken, 1996.

Georg Sander. Visualisierungstechniken für den Compilerbau. PhD thesis, Universität Saarbrücken, 1996.

Georg Sander. Graph layout for applications in compiler construction. Theoretical Computer Science, 217:175-214, 1999.

Falk Schreiber. Visualisierung biochemischer Reaktionsnetze. PhD thesis, Universität Passau, 2001.

Falk Schreiber. High quality visualization of biochemical pathways in biopath. In Silico Biology, 2(0006), 2002. http://www.bioinfo.de/isb/2002/02/0006/.

Kozo Sugiyama and Kazuo Misue. Visualization of structural information. Automatic drawing of compound digraphs. IEEE Trans. Systems, Man and Cybernetics, 21(4):876-892, 1991.

Kozo Sugiyama, Shojiro Tagawa, and Mitsuhiko Toda. Methods for visual understanding of hierarchical system structures. IEEE Trans. Systems, Man and Cybernetics, SMC-11(2):109-125, 1981.