ECCC-Report TR04-078https://eccc.weizmann.ac.il/report/2004/078Comments and Revisions published for TR04-078en-usFri, 17 Sep 2004 20:47:49 +0300
Paper TR04-078
| Two-Layer Planarization: Improving on Parameterized Algorithmics |
Henning Fernau
https://eccc.weizmann.ac.il/report/2004/078A 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.
Fri, 17 Sep 2004 20:47:49 +0300https://eccc.weizmann.ac.il/report/2004/078