Skip to main content

Research Repository

Advanced Search

Contracting planar graphs to contractions of triangulations

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

Authors

M. Kamiński

D.M. Thilikos



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
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