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 as line segments between the layers. In this paper we study the 2-LAYER PLANARIZATION problem: Can k edges be deleted from a given graph G so that the remaining graph is biplanar? This problem is script N sign ℘-complete, and remains so if the permutation of the vertices in one layer is fixed (the 1-LAYER PLANARIZATION problem). We prove that these problems are fixed-parameter tractable by giving linear-time algorithms for their solution (for fixed k). In particular, we solve the 2-LAYER PLANARIZATION problem in ο(k · 6k + |G|) time and the 1-LAYER PLANARIZATION problem in ο(3k · |G|) time. We also show that there are polynomial-time constant-approximation algorithms for both problems.

Additional Metadata
Keywords Crossing minimization, Fixed-parameter tractahility, Graph algorithms, Graph drawing, NP-complete, Planarization, Sugiyama approach
Persistent URL dx.doi.org/10.1007/s00453-005-1181-y
Journal Algorithmica
Citation
Dujmović, V, Fellows, M. (Michael), Hallett, M. (Michael), Kitching, M. (Matthew), Liotta, G. (Giuseppe), Mccartin, C. (Catherine), … Wood, D. (2006). A fixed-parameter approach to 2-layer planarization. Algorithmica, 45(2), 159–182. doi:10.1007/s00453-005-1181-y