A fixed-parameter approach to 2-layer planarization

Vida Dujmovic, Michael Fellows, Michael Hallett, Matthew Kitching, Giuseppe Liotta, Catherine McCartin, Naomi Nishimura, Prabhakar Ragde, Fran Rosamond, Matthew Suderman, Sue Whitesides, David R. Wood

Research output: Contribution to journalArticleResearchpeer-review

19 Citations (Scopus)

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 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.
Original languageEnglish
Pages (from-to)159-182
Number of pages24
JournalAlgorithmica
Volume45
Issue number2
DOIs
Publication statusPublished - 2006
Externally publishedYes

Cite this