Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR04-078 | 3rd August 2004 00:00

Two-Layer Planarization: Improving on Parameterized Algorithmics

RSS-Feed




TR04-078
Authors: Henning Fernau
Publication: 17th September 2004 20:47
Downloads: 3066
Keywords: 


Abstract:

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 variants of biplanarization problems:
- Two-Layer Planarization TLP: can $k$ edges be deleted from
a given graph $G$ so that the remaining graph is biplanar?
- One-Layer Planarizatoin OLP:
fix the order of the vertices on one layer.

Improving on earlier works of Dujmovi\'c et al.,
we solve the TLP problem in $O^*(5.19^k)$ time and the
OLP problem in $O^*(2.53^k)$ time.

Moreover, we derive a small problem kernel for OLP.



ISSN 1433-8092 | Imprint