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)

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 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
Pages1-15
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

Conference

ConferenceGraph Drawing 2001
Abbreviated titleGD 2001
CountryAustria
CityVienna
Period23/09/0126/09/01
Internet address

Cite this

Dujmovic, V., Fellows, M., Hallett, M., Kitching, M., Liotta, G., McCartin, C., Nishimura, N., Ragde, P., Rosamond, F., Suderman, M., Whitesides, S., & Wood, D. R. (2002). A fixed-parameter approach to two-layer planarization. In Graph Drawing - 9th International Symposium, GD 2001, Revised Papers (pp. 1-15). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2265 LNCS).