TY - GEN
T1 - Planar feedback vertex set and face cover
T2 - 34th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2008
AU - Koutsonas, Athanassios
AU - Thilikos, Dimitrios M.
PY - 2008
Y1 - 2008
N2 - The Planar Feedback Vertex Set problem asks, whether an n-vertex planar graph contains at most k vertices meeting all its cycles. The Face Cover problem asks, whether all vertices of a plane graph G lie on the boundary of at most k faces of G. Standard techniques from parameterized algorithm design indicate, that both problems can be solved by sub-exponential parameterized algorithms (where k is the parameter). In this paper, we improve the algorithmic analysis of both problems by proving a series of combinatorial results, relating the branchwidth of planar graphs with their face cover. Combining this fact with duality properties of branchwidth, allows us to derive analogous results on feedback vertex set. As a consequence, it follows that Planar Feedback Vertex Set and Face Cover can be solved in and steps, respectively.
AB - The Planar Feedback Vertex Set problem asks, whether an n-vertex planar graph contains at most k vertices meeting all its cycles. The Face Cover problem asks, whether all vertices of a plane graph G lie on the boundary of at most k faces of G. Standard techniques from parameterized algorithm design indicate, that both problems can be solved by sub-exponential parameterized algorithms (where k is the parameter). In this paper, we improve the algorithmic analysis of both problems by proving a series of combinatorial results, relating the branchwidth of planar graphs with their face cover. Combining this fact with duality properties of branchwidth, allows us to derive analogous results on feedback vertex set. As a consequence, it follows that Planar Feedback Vertex Set and Face Cover can be solved in and steps, respectively.
UR - http://www.scopus.com/inward/record.url?scp=58349096174&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=58349096174&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-92248-3_24
DO - 10.1007/978-3-540-92248-3_24
M3 - Conference contribution
AN - SCOPUS:58349096174
SN - 3540922474
SN - 9783540922476
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 264
EP - 274
BT - Graph-Theoretic Concepts in Computer Science - 34th International Workshop, WG 2008, Revised Papers
Y2 - 30 June 2008 through 2 July 2008
ER -