Using Sifting for k-Layer Straightline Crossing Minimization

Matuszewski, Christian and Schönfeld, Robby and Molitor, Paul (1999) Using Sifting for k-Layer Straightline Crossing Minimization. In: Graph Drawing 7th International Symposium, GD’99, September 15-19, 1999 , pp. 217-224(Official URL:

Full text not available from this repository.


We present a new algorithm for k-layer straightline crossing minimization which is based on sifting that is a heuristic for dynamic reordering of decision diagrams used during logic synthesis and formal verification of logic circuits. The experiments prove sifting to be very efficient. In particular it outperforms the traditional layer by layer sweep based heuristics known from literature by far when applied to k-layered graphs with k \ge 3.

Item Type: Conference Paper
Additional Information: 10.1007/3-540-46648-7_22
Classifications: G Algorithms and Complexity > G.700 Layering
P Styles > P.720 Straight-line
G Algorithms and Complexity > G.420 Crossings

Actions (login required)

View Item View Item