k-Layer Straightline Crossing Minimization by Speeding Up Sifting

Günther, Wolfgang and Schönfeld, Robby and Becker, Bernd and Molitor, Paul (2001) k-Layer Straightline Crossing Minimization by Speeding Up Sifting. In: Graph Drawing 8th International Symposium, GD 2000, September 20–23, 2000, Colonial Williamsburg, VA, USA , pp. 253-258 (Official URL: http://dx.doi.org/10.1007/3-540-44541-2_24).

Full text not available from this repository.

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\geq 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.

Item Type:Conference Paper
Additional Information:10.1007/3-540-44541-2_24
Classifications:M Methods > M.999 Others
G Algorithms and Complexity > G.700 Layering
G Algorithms and Complexity > G.999 Others
G Algorithms and Complexity > G.420 Crossings
ID Code:388

Repository Staff Only: item control page

References

R.E. Bryant. Graph - based algorithms for Boolean function manipulation. IEEE Trans. on Comp., 35(8):677-691, 1986.

R. Drechsler and W. Günther. Using lower bounds during dynamic BDD minimization. In Design Automation Conf., pages 29-32, 1999.

P. Eades and S. Whitesides. DRawing graphs in two layers. Theoretical Computer Science, 131:361-374, 1994.

M. Jünger and P. Mutzel. 2-layer straightline crossing minimization: Performance of exact and heuristic algorithms. Journal of Graph Algorithms and Applications, 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, 24(12):1175-1186, 1997.

C. Matuzsewski, R. Schönfeld, and P. Molitor. Using sifting for k-layer straightline crossing minimization. In Graph Drawing Conference, LNCS 1731, pages 217-224, 1999.

K. Mehlhorn and S. Näher. The LEDA Platform of Combinatorial and Geometric Computing. Cambridge University Press, 1999. Project home page at http://www.mpi-sb.mpg.de/LEDA/.

P. Mutzel, T. Ziegler, S. Näher, D. Ambras, G. Koch, M. Jünger, C. Buchheim, and S. Leipert. A library of algorithms for graph drawing. In International Symposium on Graph Drawing, LNCS 1547, pages 456-457, 1998. Project home page at http://www.mpi-sb.mpg.de/AGD/.

S. Panda and F. Somenzi. Who are the variables in your neighborhood. In Int'l Conf. on CAD, pages 74-77, 1995.

R. Rudell. Dynamic variable ordering for ordered binary decision diagrams. In Int'l Conf. on CAD, pages 42-47, 1993.