Two-Layer Planarization: Improving on Parameterized Algorithmics
Vol. 9, no. 2, pp. 205-238, 2005. Regular paper.
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 connecting vertices on one line to vertices on the other line.
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 Dujmovi\'c
et al. (
Proc. Graph Drawing GD 2001, pp. 1-15, 2002),
we solve the 2-L
AYER P
LANARIZATION problem in
O(
k2·5.1926
k+|
G|) time and the
1-L
AYER P
LANARIZATION problem in
O(
k3·2.5616
k+|
G|
2) time. Moreover, we derive a small
problem kernel for 1-L
AYER P
LANARIZATION.