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 , 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

Actions (login required)

View Item View Item