A Fast and Simple Heuristic for Constrained Two-Level Crossing Reduction

Forster, Michael (2004) A Fast and Simple Heuristic for Constrained Two-Level Crossing Reduction. In: Graph Drawing 12th International Symposium, GD 2004, September 29-October 2, 2004, New York, NY, USA , pp. 206-216 (Official URL: http://dx.doi.org/10.1007/978-3-540-31843-9_22).

Full text not available from this repository.

Abstract

The one-sided two-level crossing reduction problem is an important problem in hierarchical graph drawing. Because of its NP-hardness there are many heuristics, such as the well-known barycenter and median heuristics. We consider the constrained one-sided two-level crossing reduction problem, where the relative position of certain vertex pairs on the second level is fixed. Based on the barycenter heuristic, we present a new algorithm that runs in quadratic time and generates fewer crossings than existing simple extensions. It is significantly faster than an advanced algorithm by Schreiber [12] and Finnocchi [1,2,6], while it compares well in terms of crossing number. It is also easy to implement.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-31843-9_22
Classifications:M Methods > M.500 Layered
G Algorithms and Complexity > G.420 Crossings
P Styles > P.480 Layered
ID Code:588

Repository Staff Only: item control page

References

C. Demetrescu and I. Finocchi. Break the "right" cycles and get the "best" drawing. In B. Moret and A. Goldberg, editors, Proc. ALENEX'00, pp. 171-182, 200.

C. Demetrescu and I. Finocchi. Removing cycles for minimizing crossings. ACM Journal on Experimental Algorithmics (JEA), 6(1), 2001.

G. Di Battista, P. Eades, R. Tamassia, and I. G. Tollis. Graph Drawing: Algorithms for the Visualization of Graphs. Prentice Hall, 1999.

P. Eades, B. D. McKay, and N. C. Wormald. On an edge crossing problem. In Proc. ACSC'86, pp. 327-334. Australian National University, 1986.

P. Eades and N. C. Wormald. Edge crossings in drawings of bipartite graphs. Algorithmica, 11:379-403, 1994.

I. Finocchi. Layered drawings of graphs with crossing constraints. In J. Wang, editor, Proc. COCOON'01, volume 2108 of LNCS, pp.357-368. Springer, 2001.

M. Forster. Applying crossing reduction strategies to layered compound graphs. In S. G. Kobourov and M. T. Goodrich, editors, Proc. GD'02, volume 2528 of LNCS, pp. 276-284. Springer, 2002.

M. R. Garey and D. S. Johnson. Crossing number is NP-complete. SIAM Journal on Algebraic and Discrete Methods, 4(3):312-316, 1983.

M. Jünger and P. Mutzel. Exact and heuristic algorithms for 2-layere straightline crossing minimization. In F. J. Brandenburg, editor, Proc. GD'95, volume 1027 of LNCS, pp. 337-348. Springer, 1996.

M. Jünger and P. Mutzel. 2-layer straightline crossing minimization: Performance of exact and heuristic algorithms. JGAA, 1(1):1-25, 1997.

G. Sander. Visualisierungstechniken für den Compilerbau. PhD thesis, University of Saarbrücken, 1996.

F. Schreiber. Visualisierung biochemischer Reaktionsnetze. PhD thesis, University of Passau, 2001.

K. Sugiyama, S. Tagawa, and M. Toda. Methods for visual understanding of hierarchical system structures. IEEE Trans. SMC, 11(2):109-125, 1981.

V. Waddle. Graph layout for displaying data structures. In J. Marks, editor, Proc. GD '00, volume 1984 of LNCS, pp. 241-252. Springer, 2001.