- 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
- Hits: 997
- Visitors: 1135
- Downloads: 0