Back to Search
Start Over
Contracting planar graphs to contractions of triangulations.
- Source :
- Journal of Discrete Algorithms; Sep2011, Vol. 9 Issue 3, p299-306, 8p
- Publication Year :
- 2011
-
Abstract
- 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 such that for every fixed , there exists a linear-time algorithm deciding whether a given planar graph G can be contracted to H. The class is the closure of planar triangulated graphs under taking of contractions. In fact, we prove that a graph if and only if there exists a constant such that if the treewidth of a graph is at least , it contains H as a contraction. We also provide a characterization of in terms of minimal forbidden contractions. [Copyright &y& Elsevier]
Details
- Language :
- English
- ISSN :
- 15708667
- Volume :
- 9
- Issue :
- 3
- Database :
- Supplemental Index
- Journal :
- Journal of Discrete Algorithms
- Publication Type :
- Academic Journal
- Accession number :
- 61042995
- Full Text :
- https://doi.org/10.1016/j.jda.2011.03.010