Two-layer planarization: Improving on parameterized algorithmics

Title: Two-layer planarization: Improving on parameterized algorithmics
Creator: Fernau, Henning
Relation: SOFSEM 2005: Theory and Practice of Computer Science: 31st Conference on Current Trends in Theory and Practice of Computer Science. Proceedings. (Liptovský Ján, Slovakia January 22-28, 2005)
Publisher: Springer Verlag
Resource Type: conference paper
Date: 2005
Description: A bipartite graph is biplanar if the vertices can be placed on two parallel lines in the plane such that, there are no edge crossings when edges are drawn as straight-line segments. We study two problems: - 2-LAYER PLANARIZATION: can k edges be deleted from a given graph G so that the remaining graph is biplanar? - 1-LAYER PLANARIZATION: same question, but the order of the vertices on one layer is fixed. Improving on earlier works of Dujmovic et al. [4], we solve the 2-LAYER 'PLANARIZATION problem in O(k(2 .) 5.1926(k) + broken vertical bar G broken vertical bar) time and the 1-LAYER PLANARIZATION problem in O(k(3) (.) 2.5616(k) + broken vertical bar G broken vertical bar(2)) time. Moreover, we derive a small problem kernel for 1-LAYER PLANARIZATION.
Subject: crossing minimization
Identifier: uon:169
Identifier: http://hdl.handle.net/1959.13/25170
Identifier: ISBN:3-540-24302-X
Rights: *
Language: eng