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.