Abstract
We study the problem of finding a minimum tree spanning the faces of a given planar graph. We show that a constant factor approximation follows from the unconnected version if the minimum degree is 3. Moreover, we present a polynomial time approximation scheme for both the connected and unconnected version.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Bafna, V., Berman, P., Fujito, T.: A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem. SIAM J. Discrete Math. 12, 289–297 (1999)
Baker, B.: Approximation algorithms for NP-complete problems on planar graphs. JACM 41, 153–180 (1994)
Barnette, D.: An upper bound for the diameter of a polytope. Discr. Math. 10, 9–13 (1974)
Becker, A., Geiger, D.: Optimization of Pearl’s method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem. Artificial Intelligence 83, 167–188 (1996)
Bodlaender, H.L., Feremans, C., Grigoriev, A., Penninkx, E., Sitters, R., Wolle, T.: On the minimum corridor connection and other generalized geometric problems. In: Erlebach, T., Kaklamanis, C. (eds.) WAOA 2006. LNCS, vol. 4368, pp. 69–82. Springer, Heidelberg (2007)
Bodlaender, H.L., Grigoriev, A.: Algorithms for graphs embeddable with few crossings per edge. Algorithmica 49, 1–11 (2007)
Chudak, F.A., Goemans, M.X., Hochbaum, D.S., Williamson, D.P.: A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs. Oper. Res. Lett. 22, 111–118 (1998)
Demaine, E.D., Hajiaghayi, M.: The bidimensionality theory and its algorithmic applications. The Computer Journal 51, 292–302 (2008)
Eppstein, D.: Diameter and treewidth in minor-closed graph families. Algorithmica 27, 275–291 (2000)
Escoffier, B., Gourvès, L., Monnot, J.: Complexity and approximation results for the connected vertex cover problem. In: Brandstädt, A., Kratsch, D., Müller, H. (eds.) WG 2007. LNCS, vol. 4769, pp. 202–213. Springer, Heidelberg (2007)
Garey, M.R., Johnson, D.S.: The rectilinear Steiner tree problem is NP-complete. SIAM J. Appl. Math. 32, 826–834 (1977)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979)
Goemans, M.X., Williamson, D.P.: Primal-Dual Approximation Algorithms for Feedback Problems in Planar Graphs. Combinatorica 17, 1–23 (1997)
Savage, C.D.: Depth-first search and the vertex cover problem. Inf. Process. Lett. 14, 233–235 (1982)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Grigoriev, A., Sitters, R. (2010). Connected Feedback Vertex Set in Planar Graphs. In: Paul, C., Habib, M. (eds) Graph-Theoretic Concepts in Computer Science. WG 2009. Lecture Notes in Computer Science, vol 5911. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-11409-0_13
Download citation
DOI: https://doi.org/10.1007/978-3-642-11409-0_13
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-11408-3
Online ISBN: 978-3-642-11409-0
eBook Packages: Computer ScienceComputer Science (R0)