Two-Layer Planarization: Improving on Parameterized Algorithmics - Fernau, Henning (Journal of Graph Algorithms and Applications, 2005)
A bipartite graph is biplanar if the vertices can beplaced on two parallel lines in the plane such that there areno edge crossings when edges are drawn as straight-line segments connecting vertices on one line to vertices on the other line.We study two problems: 2-LAYER PLANARIZATION: can k edges be deleted froma given graph G so that the remaining graph is biplanar? <!----> 1-LAYER PLANARIZATION: same question, but the order of the vertices on one layeris fixed. <!----> Improving on earlier works of Dujmovi\'c et al. (Proc. Graph Drawing GD 2001, pp. 1-15, 2002),we solve the 2-LAYER PLANARIZATION problem in O(k2·5.1926k+|G|) time and the 1-LAYER PLANARIZATION problem in O(k3·2.5616k+|G|2) time. Moreover, we derive a smallproblem kernel for 1-LAYER PLANARIZATION. <!---->