2010/12/11 by Marcin Kaminski, Kaminski, Marcin, Daniel Paulusma +3
Computer Science · Mathematics · #05C85 #68R10 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.2.1 #acm:05C85 #acm:68R10 #cs.DM #math.CO #msc:05C85 #msc:68R10
paper · pdf · doi:10.48550/arxiv.1012.2460
11 pages, 3 figues
arxiv created 2010/12/11 · arxiv updated 2010/12/14
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. In this paper, we identify a class of graphs \cal C such that for every H ∈ \cal C, there exists an algorithm deciding in time f(|V(H)|) ⋅ |V(G)|^\bigO1 whether a planar graph G can be contracted to~H. (The function f(⋅) does not depend on G.) The class \cal C is the closure of planar triangulated graphs under taking of contractions. In fact, we prove that a graph H ∈ \cal C if and only if there exists a constant cH such that if the tree-width of a graph is at least cH, it contains H as a contraction. We also provide a characterization of \cal C in terms of minimal forbidden contractions.