Article ID Journal Published Year Pages File Type
431044 Journal of Discrete Algorithms 2011 8 Pages PDF
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
, , ,