Contracting planar graphs to contractions of triangulations

Kamiński, M.; Paulusma, D.; Thilikos, D.M.

Abstract

For every graph H, there exists a polynomial-time algorithm deciding if a planar input graph G can be contracted to H. However, the degree of the polynomial depends on the size of H. We identify a class of graphs C such that for every fixed H∈C, there exists a linear-time algorithm deciding whether a given planar graph G can be contracted to H. The class C is the closure of planar triangulated graphs under taking of contractions. In fact, we prove that a graph H∈C if and only if there exists a constant cH such that if the treewidth of a graph is at least cH, it contains H as a contraction. We also provide a characterization of C in terms of minimal forbidden contractions.

Citation

Kamiński, M., Paulusma, D., & Thilikos, D. (2011). Contracting planar graphs to contractions of triangulations. Journal of discrete algorithms, 9(3), 299-306. https://doi.org/10.1016/j.jda.2011.03.010

• Journal Article Type: Article
• Publication Date: Sep 1, 2011
• Deposit Date: Dec 6, 2011
• Journal: Journal of Discrete Algorithms
• Print ISSN: 1570-8667
• Electronic ISSN: 1570-8675
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 9
• Issue: 3
• Pages: 299-306
• DOI: https://doi.org/10.1016/j.jda.2011.03.010
• Keywords: Planar graph, Dual graph, Contraction, Topological minor, Fixed parameter tractable.
• Public URL: https://durham-repository.worktribe.com/output/1501858