Abstract
We exhibit a small problem kernel for the problem one-sided crossing minimization which plays an important role in graph drawing algorithms based on the Sugiyama layering approach. Moreover, we improve on the search tree algorithm developed in [5] and derive an O(1.4656k + kn 2) algorithm for this problem, where k upperbounds the number of tolerated crossings of straight lines involved in the drawings of an n-vertex graph. Relations of this graph-drawing problem to the algebraic problem of finding a weighted linear extension of an ordering similar to [7] are exhibited.
Chapter PDF
Similar content being viewed by others
References
Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: Algorithms for the Visualization of Graphs. Prentice Hall, Englewood Cliffs (1999)
Downey, R., Fellows, M.: Parameterized Complexity. Springer, Heidelberg (1999)
Dujmović, V., Fellows, M., Hallet, M., Kitching, M., Liotta, G., McCartin, C., Nishimura, N., Ragde, P., Rosemand, F., Suderman, M., Whitesides, S., Wood, D.: An efficient fixed parameter approach to two-layer planarization. In: Mutzel, P., Jünger, M., Leipert, S. (eds.) GD 2001. LNCS, vol. 2265, pp. 1–15. Springer, Heidelberg (2002)
Dujmović, V., Fellows, M., Hallet, M., Kitching, M., Liotta, G., McCartin, C., Nishimura, N., Ragde, P., Rosemand, F., Suderman, M., Whitesides, S., Wood, D.: On the parameterized complexity of layered graph drawing. In: Meyer auf der Heide, F. (ed.) ESA 2001. LNCS, vol. 2161, pp. 488–499. Springer, Heidelberg (2001)
Dujmović, V., Whitesides, S.: An efficient fixed parameter tractable algorithm for 1-sided crossing minimization. In: Goodrich, M.T., Kobourov, S.G. (eds.) GD 2002. LNCS, vol. 2528, pp. 118–129. Springer, Heidelberg (2002)
Eades, P., Wormald, N.C.: Edge crossings in drawings of bipartite graphs. Algorithmica 11, 379–403 (1994)
Jünger, M., Mutzel, P.: 2-layer straightline crossing minimization: performance of exact and heuristic algorithms. J. Graph Algorithms Appl. 1, 1–25 (1997)
Munoz, X., Unger, W., Vrto, I.: One sided crossing minimization is NP-hard for sparse graphs. In: Mutzel, P., Jünger, M., Leipert, S. (eds.) GD 2001. LNCS, vol. 2265, pp. 115–123. Springer, Heidelberg (2002)
Niedermeier, R., Rossmanith, P.: A general method to speed up fixed-parametertractable algorithms. Information Processing Letters 73, 125–129 (2000)
Sugiyama, K., Tagawa, S., Toda, M.: Methods for visual understanding of hierarchical system structures. IEEE Transactions on Systems, Man and Cybernetics 11, 109–125 (1981)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dujmović, V., Fernau, H., Kaufmann, M. (2004). Fixed Parameter Algorithms for one-sided crossing minimization Revisited. In: Liotta, G. (eds) Graph Drawing. GD 2003. Lecture Notes in Computer Science, vol 2912. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24595-7_31
Download citation
DOI: https://doi.org/10.1007/978-3-540-24595-7_31
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-20831-0
Online ISBN: 978-3-540-24595-7
eBook Packages: Springer Book Archive