# zbMATH — the first resource for mathematics

New algorithms for $$k$$-face cover, $$k$$-feedback vertex set, and $$k$$-disjoint cycles on plane and planar graphs. (English) Zbl 1022.68100
Kučera, Luděk (ed.), Graph-theoretic concepts in computer science. 28th international workshop, WG 2002, Český Krumlov, Czech Republic, June 13-15, 2002. Revised papers. Berlin: Springer. Lect. Notes Comput. Sci. 2573, 282-295 (2002).
Summary: We present new fixed parameter algorithms for the FACE COVER problem on plane graphs. We show that if a plane graph has a face cover with at most $$k$$ faces then its treewidth is bounded by $$O(\sqrt{k})$$. An approximate tree decomposition can be obtained in linear time, and this is used to find an algorithm computing the face cover number in time $$O(c^{\sqrt{k}} n)$$ for some constant $$c$$. Next we show that the problem is in linear time reducible to a problem kernel of $$O(k^{2})$$ vertices, and this kernel can be used to obtain an algorithm that runs in time $$O(c^{\sqrt{k}}+n)$$ for some other constant $$c$$. For the $$k$$-DISJOINT CYCLES problem and the $$k$$-FEEDBACK VERTEX SET problem on planar graphs we obtain algorithms that run in time $$O(c^{\sqrt{k}\log{k}}n)$$ for some constant $$c$$. For the $$k$$-FEEDBACK VERTEXS ET problem we can further reduce the problem to a problem kernel of size $$O(k^{3})$$ and obtain an algorithm that runs in time $$O(c^{\sqrt{k}\log{k}}+n)$$ for some constant $$c$$.
For the entire collection see [Zbl 1013.00032].

##### MSC:
 68R10 Graph theory (including graph drawing) in computer science 05C85 Graph algorithms (graph-theoretic aspects) 68Q25 Analysis of algorithms and problem complexity
Full Text: