A Fixed-Parameter Approach to Two-Layer Planarization

Dujmović, Vida and Fellows, M. and Hallett, M. and Kitching, Matthew and Liotta, Giuseppe and McCartin, C. and Nishimura, N. and Ragde, P. and Rosamond, F. and Suderman, Matthew and Whitesides, Sue and Wood, David R. (2002) A Fixed-Parameter Approach to Two-Layer Planarization. In: Graph Drawing 9th International Symposium, GD 2001, September 23-26, 2001, Vienna, Austria , pp. 1-15 (Official URL: http://dx.doi.org/10.1007/3-540-45848-4_1).

Full text not available from this repository.


A bipartite graph is biplanar if the vertices can be placed on two parallel lines (layers) in the plane such that there are no edge crossings when edges are drawn straight. The 2-LAYER PLANARIZATION problem asks if k edges can be deleted from a given graph G so that the remaining graph is biplanar. This problem is NP-complete, as is the 1-LAYER PLANARIZATION problem in which the permutation of the vertices in one layer is fixed. We give the following fixed parameter tractability results: an O(k \centerdot 6^k+|G|) algorithm for 2-LAYER PLANARIZATION and an O(3^k\centerdot |G|) algorithm for 1-LAYER PLANARIZATION, thus achieving linear time for fixed k.

Item Type:Conference Paper
Additional Information:10.1007/3-540-45848-4_1
Classifications:G Algorithms and Complexity > G.420 Crossings
G Algorithms and Complexity > G.700 Layering
G Algorithms and Complexity > G.840 Planarization
ID Code:368

Repository Staff Only: item control page


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.

V. Dujmovic, 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 Symp. on Algorithms (ESA '01), to appear.

P. Eades, B.D. McKay, and N.C. Wormland. On an edge crossing problem. In Proc. 9th Australian Computer Science Conference, pages 327-334. Australian National University, 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.

F. Harary and A. Schwenk. A new crossing number of bipartite graphs. Utilitas Math., 1:203-209, 1972.

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

M. Kaufmann and D. Wagner, editors. Drawing Graphs: Methods and Models, volume 2025 of Lecture Notes in Comput. Sci. Springer, 2001.

T. Lengauer. Combinatorial Algorithms for Integrated Circuit Layout. Wiley, 1990.

P. Mutzel. An alternative method to crossing minimzation on hierarchical graphs. SIAM J. Optimization, 11(4):1065-1080, 2001.

P. Mutzel. Optimization in leveled graphs. In P.M. Pardalos and C.A. Floudas, editors, Encyclopedia of Optimization, Kluwer, to appear.

P. Mutzel and R. Weiskircher. Two-layer planarization in graph drawing. In K.Y. Chwa and O.H. Ibarra, editors, Proc. 9th International Symp. on Algorithms and Computation (ISAAC'98), volume 1533 of Lecture Notes in Comput. Sci., pages 69-78. Springer, 1998.

F. Shahrokhi, O. Sýkora, L.A. Székely, and I. Vrto. On bipartite drawings and the linear arrangement problem. SIAM J. Comput., 30(6):1773-1789, 2001.

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

N. Tomii, Y. Kambayashi, and S. Yajima. On planarization algorithms for 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 algorithm for minimizing the number of crossing arcs in bipartite graphs. J. Operat. Res., 90:303-3019, 1996.

M.S. Waterman and J.R. Griggs. Interval graphs and maps of DNA. Bull. Math. Biol., 48(2):189-195, 1986.