An Efficient Fixed Parameter Tractable Algorithm for 1-Sided Crossing Minimization

Dujmović, Vida and Whitesides, Sue (2002) An Efficient Fixed Parameter Tractable Algorithm for 1-Sided Crossing Minimization. In: Graph Drawing 10th International Symposium, GD 2002, August 26-28, 2002, Irvine, CA, USA , pp. 118-129 (Official URL: http://dx.doi.org/10.1007/3-540-36151-0_12).

Full text not available from this repository.

Abstract

We give an O(øk · n 2) algorithm for the 1-SIDED CROSSING MINIMIZATION problem, thus showing that the problem is Fixed Parameter Tractable. The constant \phi in the running time is the golden ratio \phi=\frac{1+\sqrt{5}}{2}\approx 1.618. The constant k is the parameter of the problem: the number of allowed edge crossings.

Item Type:Conference Paper
Additional Information:10.1007/3-540-36151-0_12
Classifications:M Methods > M.999 Others
Z Theory > Z.999 Others
G Algorithms and Complexity > G.420 Crossings
ID Code:294

Repository Staff Only: item control page

References

M.J. Carpano. Automatic display of hierarchized graphs for computer aided decision analysis. IEEE Trans. Syst. Man Cybern., SMC-10(11):705-715, 1980.

C. Catarci. The assignment heuristic for crossing reduction. IEEE Trans. on Systems, Man, and Cybernetics, 25(3), 1995.

T. Corman, C. Leiserson, and R. Rivest. Introduction to Algorithms. MIT Press, 1990.

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

R.G. Downey and M.R. Fellows. Parametrized complexity. Springer, 1999.

S. Dresbach. A new heuristic layout algorithm for directed acyclic graphs. In U. Derig, A. Bachem, and A.B.A. Drexl, editors, Operations Research Proceedings (1994), pages 121-126. Springer, 1995.

V. Djumovic, M. Fellows, M. Hallett, M. Kitching, G. Liotta, C. McCartin, N. Nishimura, P. Ragde, F. Rosemand, M, Suderman, S. Whitesides, and D.R. Wood. A fixed-parameter approach to two-layer planarization. In: Mutzel editor. Proc. Graph Drawing: 9th International Symposium (GD '01), volume 2265 of Lecture Notes in Comput. Sci. Springer, 2001. pages 1-15.

V. Djumovic, M. Fellows, M. Hallett, M. Kitching, G. Liotta, C. McCartin, N. Nishimura, P. Ragde, F. Rosemand, M, Suderman, S. Whitesides, and D.R. Wood. On the parameterized complexity of layered graph drawing. In Proc. 9th European Symposium on Algorithms (ESA 2001), volume 2161 of Lecture Notes in Computer Sci., pages 488-499. Springer, 2001.

P. Eades and D. Kelly. Heuristics for drawing 2-layered networks. Ars Combin., 21(A):89-98, 1986.

P. Eades and S. Whitesides. Drawing graphs in two layers. Theoret. Comput. Sci., 131(2):361-374, 1994.

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

M.R. Garey and D.S. Johnson. Crossing number is NP-complete. SIAM J. Algebraic Discrete Methods, 4(3):312-316, 1983.

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

X Muñoz, U Unger, and I Vrto. One sided crossing minimization is np-hard for sparse graphs. In Mutzel [15]. to appear.

P. Mutzel, editor. Proc. Graph Drawing: 9th International Symposium (GD '01), volume 2265 of Lecture Notes in Comput. Sci. Springer, 2001.

K. Sugiyama, S. Tagawa, and M. Toda. Methods for visual understanding of hierarchical system structures. IEEE Trans. Systems Man Cybernet., 11(2):109-125, 1981.

N. Tomii, Y. Kambayashi, and S. Yajima. On planarization algorithms of 2-level graphs. Papers of tech. group on elect. comp. IECEJ, EC77-38:1-12, 1977.

V. Valls, R. Marti, and P. Lino. A branch and bound algorihm for minimizing the number of crossing arcs in bipartite graphs. J. Operational Res., 90:303-319, 1996.

J.N. Warfield. Crossing theory and hierarchy mapping. IEEE Trans. Systems Man Cybernet., SMC-7(7):505-523, 1977.