zbMATH — the first resource for mathematics

A fixed-parameter approach to two-layer planarization. (English) Zbl 1054.68576
Mutzel, Petra (ed.) et al., Graph drawing. 9th international symposium, GD 2001, Vienna, Austria, September 23–26, 2001. Revised papers. Berlin: Springer (ISBN 3-540-43309-0). Lect. Notes Comput. Sci. 2265, 1-15 (2002).
Summary: A bipartite graph is biplanar if the vertices can be placed on two parallel lines (layers) in the plane such that there are no edge crossings when edges are drawn straight. The 2-LAYER PLANARIZATION problem asks if \(k\) edges can be deleted from a given graph \(G\) so that the remaining graph is biplanar. This problem is NP-complete, as is the 1-LAYER PLANARIZATION problem in which the permutation of the vertices in one layer is fixed. We give the following fixed parameter tractability results: an \(O(k\cdot6^k+| G|)\) algorithm for 2-LAYER PLANARIZATION and an \(O(3^k\cdot| G|)\) algorithm for 1-LAYER PLANARIZATION, thus achieving linear time for fixed \(k\).
For the entire collection see [Zbl 0984.00060].

68R10 Graph theory (including graph drawing) in computer science
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
05C85 Graph algorithms (graph-theoretic aspects)
Full Text: Link