__
TR04-078 | 3rd August 2004 00:00
__

#### Two-Layer Planarization: Improving on Parameterized Algorithmics

**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.