Eschbach, Thomas and Günther, Wolfgang and Drechsler, Rolf and Becker, Bernd (2002) Crossing Reduction by Windows Optimization. [Conference Paper]
Full text not available from this repository.
Abstract
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 |
|---|---|
| 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 |
| Deposited By: | Martinez Leon, Victoria |
| Deposited On: | 07 Dec 2004 |
| Last Modified: | 18 Sep 2008 13:08 |
| Alternative Locations: | http://www.springerlink.com/openurl.asp?genre=article&issn=0302-9743&volume=2528&spage=285 |
Repository Staff Only: item control page
