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.

, , , , , ,
doi.org/10.1007/s00453-005-1181-y
Algorithmica
School of Computer Science

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