20060601
A fixedparameter approach to 2layer planarization
Publication
Publication
Algorithmica , Volume 45  Issue 2 p. 159 182
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 2LAYER 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 1LAYER PLANARIZATION problem). We prove that these problems are fixedparameter tractable by giving lineartime algorithms for their solution (for fixed k). In particular, we solve the 2LAYER PLANARIZATION problem in ο(k · 6k + G) time and the 1LAYER PLANARIZATION problem in ο(3k · G) time. We also show that there are polynomialtime constantapproximation algorithms for both problems.
Additional Metadata  

, , , , , ,  
doi.org/10.1007/s004530051181y  
Algorithmica  
Organisation  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 fixedparameter approach to 2layer planarization. Algorithmica, 45(2), 159–182. doi:10.1007/s004530051181y
