
arXiv: 1012.2460
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 \in \cal C$, there exists an algorithm deciding in time $f(|V(H)|) \cdot |V(G)|^{\bigO{1}}$ whether a planar graph $G$ can be contracted to~$H$. (The function $f(\cdot)$ 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 \in \cal C$ if and only if there exists a constant $c_H$ such that if the tree-width of a graph is at least $c_H$, it contains $H$ as a contraction. We also provide a characterization of $\cal C$ in terms of minimal forbidden contractions.
11 pages, 3 figues
FOS: Computer and information sciences, Discrete Mathematics (cs.DM), planar graph, G.2.1, topological minor, Planar graphs; geometric and topological aspects of graph theory, Theoretical Computer Science, Planar graph, dual graph, Graph algorithms (graph-theoretic aspects), Informatique mathématique, FOS: Mathematics, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, Dual graph, Topological minor, Contraction, contraction, fixed parameter tractable, Mathématiques, Computational Theory and Mathematics, 68R10, 05C85, Graph theory (including graph drawing) in computer science, Combinatorics (math.CO), Fixed parameter tractable, Computer Science - Discrete Mathematics
FOS: Computer and information sciences, Discrete Mathematics (cs.DM), planar graph, G.2.1, topological minor, Planar graphs; geometric and topological aspects of graph theory, Theoretical Computer Science, Planar graph, dual graph, Graph algorithms (graph-theoretic aspects), Informatique mathématique, FOS: Mathematics, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, Dual graph, Topological minor, Contraction, contraction, fixed parameter tractable, Mathématiques, Computational Theory and Mathematics, 68R10, 05C85, Graph theory (including graph drawing) in computer science, Combinatorics (math.CO), Fixed parameter tractable, Computer Science - Discrete Mathematics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 2 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
