Name
Abstract | ||
|---|---|---|
Recently, a technique called sifting has been proposed for k- layer straightline crossing minimization. This approach outperforms the traditional layer by layer sweep based heuristics by far when applied to k-layered graphs with k ≥ 3. In this paper, we present two methods to speed up sifting. First, it is shown how the crossing matrix can be computed and updated efficiently. Then, we study lower bounds which can be incorporated in the sifting algorithm, allowing to prune large parts of the search space. Experimental results show that it is possible to speed up sifting by more than a factor of 20 using the new methods. |
Year | DOI | Venue |
|---|---|---|
2000 | 10.1007/3-540-44541-2_24 | Graph Drawing |
Keywords | Field | DocType |
large part,k-layered graph,search space,layer sweep,new method,traditional layer,layer straightline,k-layer straightline crossing minimization,lower bound,sifting algorithm,layer by layer | Graph,Discrete mathematics,Combinatorics,Matrix (mathematics),Computer science,Directed graph,Algorithm,Heuristics,Minification,Speedup | Conference |
ISBN | Citations | PageRank |
3-540-41554-8 | 3 | 0.44 |
References | Authors | |
11 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Wolfgang Günther | 1 | 7 | 3.28 |
| Robby Schönfeld | 2 | 37 | 2.79 |
| Bernd Becker | 3 | 345 | 31.68 |
| P. Molitor | 4 | 211 | 18.50 |