Two-Layer Planarization: Improving on Parameterized Algorithmics

Authors

  • Henning Fernau

DOI:

https://doi.org/10.7155/jgaa.00106

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-LAYER PLANARIZATION problem in O(k2·5.1926k+|G|) time and the 1-LAYER PLANARIZATION problem in O(k3·2.5616k+|G|2) time. Moreover, we derive a small problem kernel for 1-LAYER PLANARIZATION.

Downloads

Download data is not yet available.

Downloads

Published

2005-01-01

How to Cite

Fernau, H. (2005). Two-Layer Planarization: Improving on Parameterized Algorithmics. Journal of Graph Algorithms and Applications, 9(2), 205–238. https://doi.org/10.7155/jgaa.00106

Issue

Section

Articles

Categories