Abstract
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 2Layer Planarization problem asks if k edges can be deleted from a given graph G so that the remaining graph is biplanar. This problem is NPcomplete, as is the 1Layer 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 · 6 ^{k} + G) algorithm for 2Layer Planarization and an O(3 ^{k} · G) algorithm for 1Layer Planarization, thus achieving linear time for fixed k.
Original language  English 

Title of host publication  Graph Drawing  9th International Symposium, GD 2001, Revised Papers 
Pages  115 
Number of pages  15 
Publication status  Published  1 Dec 2002 
Externally published  Yes 
Event  Graph Drawing 2001  Vienna, Austria Duration: 23 Sep 2001 → 26 Sep 2001 Conference number: 9th https://link.springer.com/book/10.1007/3540458484 (Proceedings) 
Publication series
Name  Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 

Volume  2265 LNCS 
ISSN (Print)  03029743 
ISSN (Electronic)  16113349 
Conference
Conference  Graph Drawing 2001 

Abbreviated title  GD 2001 
Country  Austria 
City  Vienna 
Period  23/09/01 → 26/09/01 
Internet address 
