Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
431044 | Journal of Discrete Algorithms | 2011 | 8 Pages |
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 CC such that for every fixed H∈CH∈C, there exists a linear-time algorithm deciding whether a given planar graph G can be contracted to H . The class CC is the closure of planar triangulated graphs under taking of contractions. In fact, we prove that a graph H∈CH∈C if and only if there exists a constant cHcH such that if the treewidth of a graph is at least cHcH, it contains H as a contraction. We also provide a characterization of CC in terms of minimal forbidden contractions.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Marcin Kamiński, Daniël Paulusma, Dimitrios M. Thilikos,