Abstract
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 VERTEX SET 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 1.
Supported by an EPSRC grant. Kaleidoscopic address: ton@cs.rhul.ac.uk.
Corresponding author.
Supported by NSERC of Canada.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alber, J., H. Bodlaender, H. Fernau, and R. Niedermeier, Faster algorithms for domination of planar graphs, Proc. of the 17th SWAT’00, Springer-Verlag LNCS 1851 (2000), pp. 97–110.
Alber, J., H. Fan, M. Fellows, H. Fernau, R. Niedermeier, F. Rosamond, U. Stege, Refined search tree techniques for the planar dominating set problem, Proceedings26th MFCS 2001.
Alber, Jochen, Henning Fernau, and Rolf Niedermeier, Parameterized complexity: Exponential speed-up for planar graph problems, Proceedings 28th ICALP, 2001.
Alber, J., H. Fernau, R. Niedermeier, Graph separators: A parameterized view, Proceedings 7th COCOON 2001.
Bodlaender, Hans, L., On disjoint cycles, International Journal of Foundation of Computer Science 5, (1994), pp. 59–68.
Bodlaender, H., A linear time algorithm for finding tree decompositions of small treewidth, SIAM J. Comput. 25, (1996), pp. 1305–1317.
Bodlaender, Hans L., Ton Kloks, Jochen Alber, Henning Fernau, and Rolf Niedermeier, Faster algorithms for planar dominating set and related problems, 40th Workshop Komplexitätstheorie, Datenstrukturen und Effiziente Algorithmen, Technische Universität Ilmenau, 2000.
Cai, Liming and D. W. Juedes, Subexponential parameterized algorithms collapse the W-hierarchy, Proceedings 28th ICALP, 2001.
Cai, Liming, Michael Fellows, David Juedes, and Frances Rosamond, Efficient polynomial-time approximation schemes for problems on planar structures: upper and lowerbounds. Manuscript 2001.
Chang M.-S, T. Kloks, and C. M. Lee, Maximum clique transversals, Proceedings 27th WG 2001, Springer-Verlag LNCS 2204 (2001), pp. 32–43.
Bollobás, B., Graphs without two independent circuits, (Hungarian), K. Mat. Lapok 15, (1964), pp. 311–321.
Diestel, R., Graph Theory, Springer-Verlag, New York, 1997.
Downey, Rod G. and Mike R. Fellows, Parameterized complexity, Monographs in Computer Science, Springer-Verlag, 1999.
Downey, R. G. and M. R. Fellows, Parameterized computational feasibility, Proceedings of feasible mathematics II (eds. P. Clote and J. B. Remmel), Birkhauser (1995), pp. 219–244.
Erdös, P. and L. Pósa, On independent circuits contained in a graph, Canad. J. Math. 17, (1964), pp. 347–352.
Fellows, M. R. and M. A. Langston, Nonconstructive tools for proving polynomial time decidability,J. ACM 35, (1988), pp. 727–739.
Mohar, Bojan, Face covers and the genus problem for apex graphs, Journal of Combinatorial Theory, Series B 82, (2001), pp. 102–117.
Telle, Jan Arne and Andrezj Proskurowski, Efficient sets in partial k-trees, Discrete Applied Math. 44, (1993), pp. 109–117.
Kloks, T., Treewidth-Computations and approxmations, Springer-Verlag, LNCS 842, 1994.
Voss, H. J., Some properties of graphs containing k independent circuits, Proc. Colloq. Tihany, Academic Press, New York, 1968, pp. 321–334.
Voss, H. J., Über die Taillenweite in Graphen, die maximal unabhängige Kreise enthalten, und über die Anzahl der Knotenpunkte, die alle Kreise repräsentieren, X. Internat. Wiss. Koll. TH Ilmenau 1965 Heft 11, Mathematische Probleme der Ökonomie und Rechentechnik, Vortragsreihe, 23–27.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kloks, T., Lee, C., Liu, J. (2002). New Algorithms for k-Face Cover, k-Feedback Vertex Set, and k-Disjoint Cycles on Plane and Planar Graphs. In: Goos, G., Hartmanis, J., van Leeuwen, J., Kučera, L. (eds) Graph-Theoretic Concepts in Computer Science. WG 2002. Lecture Notes in Computer Science, vol 2573. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36379-3_25
Download citation
DOI: https://doi.org/10.1007/3-540-36379-3_25
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-00331-1
Online ISBN: 978-3-540-36379-8
eBook Packages: Springer Book Archive