Fixed Parameter Algorithms for one-sided crossing minimization Revisited

Dujmovic, Vida and Fernau, Henning and Kaufmann, Michael (2004) Fixed Parameter Algorithms for one-sided crossing minimization Revisited. In: Graph Drawing 11th International Symposium, GD 2003, September 21-24, 2003, Perugia, Italy , pp. 332-344 (Official URL: http://dx.doi.org/10.1007/978-3-540-24595-7_31).

Full text not available from this repository.

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.4656^{k} + 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.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-24595-7_31
Classifications:G Algorithms and Complexity > G.420 Crossings
P Styles > P.480 Layered
ID Code:463

Repository Staff Only: item control page

References

Di Battista G., Eades P., Tamassia R. and I.G. Tollis, Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall, 1999.

R. Downey and M. Fellows. Parameterized Complexity, Springer, 1999.

V. Dujmovic, M. Fellows, M. Hallet, M. Kitching, G. Liotta, C. McGartin, N. Nishimura, P. Ragde, F. Rosemand, M. Suderman, S. Whitesides, and D. Wood, An efficient fixed parameter approach to two-layer planarization. In P. Mutzel and M. Jünger, eds., Graph Drawing GD '01, LNCS 2265, pages 1-15. Springer, 2001.

V. Dujmovic, M. Fellows, M. Hallet, M. Kitching, G. Liotta, C. McGartin, N. Nishimura, P. Ragde, F. Rosemand, M. Suderman, S. Whitesides, and D. Wood, On the parameterized complexity of layered graph drawing, In F. Meyer auf der Heide, ed., European Symposium on Algorithms ESA '01, LNCS 2161, pages 488-499. Springer, 2001.

V. Dujmovic and S. Whitesides. An efficient fixed parameter tractable algorithm for 1-sided crossing minimization. In M. T. Goodrich and S. G. Kobourov, eds., Graph Drawing GD'92, LNCS 2528, pages 118-129. Springer, 2002.

P. Eades and N. C. Wormald. Edge crossings in drawings of bipartite graphs. Algorithmica, 11:379-403, 1994.

M. Jünger and P. Mutzel. 2-layer straightline crossing minimization: performance of exact and heuristic algorithms. J. Graph Algorithms Appl., 1:1-25, 1997.

X. Munoz, W. Unger, and I. Vrto, One sided crossing minimization is NP-hard for sparse graphs. In P. Mutzel and M. Jünger, eds., Graph Drawing GD'01, LNCS 2265, pages 115-123. Springer, 2001.

R. Niedermeier and P. Rossmanith. A general method to speed up fixed-parameter-tractable algorithms. Information Processing Letters, 73:125-129, 2000.

Sugijama K., S. Tagawa and M. Toda. Methods for visual understanding of hierarchical system structures, IEEE Transactions on Systems, Man and Cybernetics, 11:109-125, 1981.