A fixed-parameter approach to two-layer planarization

V. Dujmovic, M. Fellows, M. Hallett, M. Kitching, Giuseppe Liotta, C. McCartin, N. Nishimura, P. Ragde, F. Rosamond, M. Suderman, S. Whitesides, David R. Wood

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

17 Citations (Scopus)


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

Original languageEnglish
Title of host publicationGraph Drawing - 9th International Symposium, GD 2001, Revised Papers
Number of pages15
Publication statusPublished - 1 Dec 2002
Externally publishedYes
EventGraph Drawing 2001 - Vienna, Austria
Duration: 23 Sep 200126 Sep 2001
Conference number: 9th
https://link.springer.com/book/10.1007/3-540-45848-4 (Proceedings)

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2265 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


ConferenceGraph Drawing 2001
Abbreviated titleGD 2001
Internet address

Cite this