Crossing Reduction by Windows Optimization

Eschbach, Thomas and Günther, Wolfgang and Drechsler, Rolf and Becker, Bernd (2002) Crossing Reduction by Windows Optimization. In: Graph Drawing 10th International Symposium, GD 2002, August 26-28, 2002, Irvine, CA, USA , pp. 285-294 (Official URL:

Full text not available from this repository.


The number of edge crossings is a commonly accepted measure to judge the "readability" of graph drawings. In this paper we present a new algorithm for high quality multi-layer straight-line crossing minimization. The proposed method uses a local optimization technique where subsets of nodes and edges are processed exactly. The algorithm uses optimization on a window applied in a manner, similar to those used in the area of formal verification of logic circuits. In contrast to most existing heuristics, more than two layers are considered simultaneously. The algorithm tries to reduce the total number of crossings based on an initial placement of the nodes and can thus also be used in a post-processing step. Experiments are given to demonstrate the efficacy of the proposed technique on benchmarks from the area of circuit design.

Item Type:Conference Paper
Additional Information:10.1007/3-540-36151-0_27
Classifications:G Algorithms and Complexity > G.700 Layering
P Styles > P.720 Straight-line
G Algorithms and Complexity > G.420 Crossings
P Styles > P.480 Layered
ID Code:348

Repository Staff Only: item control page


G. Di Battista, P. Eades, R. Tamassia, and I.G. Tollis. Algorithms for Drawing Graphs: An annotated bibliography. Computational Geometry: Theory and Applications, 4:235-282, 1994.

F. Brglez, D. Bryan, and K. Kozminski. Combinattional Profiles of Sequential Benchmark Circuits. Int'l Symp. Circ. and Systems, 1924-1934, 1989.

R. Drechsler, W. Günther, L. Linhard, and G. Angst. Level Assignment for Displaying Combinatorial Logic. In EUROMICRO, 148-151, 2001.

P. Eades, and D. Kelly. Heuristics for reducing crossings in 2-layered networks. Ars Combin., 21.A:89-98, 1986.

P. Eades, and K. Sugiyama, How to draw a Directed Graph. Journal of Information Processing, Vol.13, 4, 424-437, 1991.

M. Fujita, Y. Matsunaga, and T. Kakuda. On Variable Ordering of Binary Decision Diagrams for the Application of Multi-Level Synthesis. European Conf. on Design Automation, 50-54, 1991.

M.R. Garey, and D.S. Johnson. Crossing number is NP-Complete. SIAM Journal on Algebraic and Discrete Methods, 4:312-346, 1983.

W. Günther, R. Schönfeld, B. Becker, and P. Molitor. K-Layer Straightline Crossing Minimization by Speeding up Sifting. Proceedings of the 8th International Symposium on Graph Drawing, 253-258, 2000.

N. Ishiura, H. Sawada, and S. Yajima. Minimization of Binary Decision Diagrams Based on Exchange of Variables . Int'l Conf. on CAD, 472-475, 1991.

M. Jünger, E.K. Lee, P. Mutzel, and T. Odenthal. A Polyhedral Approach to the Multi-Layer Crossing Number Problem. Proceedings of the 5th International Symposium on Graph Drawing, LNCS Vol. 1353, 13-24, 1997.

M. Jünger and P. Mutzel. 2-Layer Straightline Crossing Minimization: Performance of Exact and Heuristic Algorithms. J. Graph Algorithms Appl., 1(1):1-25, 1997.

M. Laguna, R. Martí, and V. Valls. Arc Crossing Minimization in Hierarchical Digraphs with Tabu Search. Computers and Operations Research, Vol. 24,2:1175-1186, 1997.

E. Mäkinen. Experiments on drawing 2-level hierarchical graphs. International Journal of Computer and Mathematics, 36:175-181, 1990.

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

C. Matuszewski, R. Schönfeld, and P. Molitor. Using Sifting for k-Layer straightline crossing minimization. Proceedings of the 7th International Symposium on Graph Drawing, LNCS 1731, 217-224, 1999.

K. McElvain Benchmark Set: Version 4.0. International Workshop on Logic Synthesis, 1993.

K. Mehlhorn, and S. Näher. LEAD: A Platform for Combinatorial and Geometric Computing. Communications of the ACM, 38, 1:96-102, 1995.

P. Mutzel. An Alternative Method for Crossing Minimization on Hierarchical Graphs. SIAM Journal on Optimization , 11, 4, 1065-1080, 2001.

P. Mutzel, C. Gutwenger, R. Brockenauer, S. Fialko, G.W. Klau, M. Krüger, T. Ziegler, S. Näher, D. Alberts, D. Ambras, G. Koch, M. Jünger, C. Buchheim, and S. Leipert. AGD: A Library of Algorithms for Graph Drawing. Proceedings of the 6th International Symposium on Graph Drawing, LNCS 1547, 456-457, 1998.

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

J. Warfield. Crossing Theory and Hierarchy Mapping. IEEE Transactions on System, Man, and Cybernetics, SMC-7, 7, 502-523, 1977.