skip to main content

Contracting planar graphs to contractions of triangulations

Kamiński, Marcin ; Paulusma, Daniël ; Thilikos, Dimitrios M.

Journal of Discrete Algorithms, 2011, Vol.9(3), pp.299-306 [Periódico revisado por pares]

Texto completo disponível

Ver todas as versões
Citações Citado por
  • Título:
    Contracting planar graphs to contractions of triangulations
  • Autor: Kamiński, Marcin ; Paulusma, Daniël ; Thilikos, Dimitrios M.
  • Assuntos: Planar Graph ; Dual Graph ; Contraction ; Topological Minor ; Fixed Parameter Tractable
  • É parte de: Journal of Discrete Algorithms, 2011, Vol.9(3), pp.299-306
  • Descrição: 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 C such that for every fixed H ∈ C , there exists a linear-time algorithm deciding whether a given planar graph G can be contracted to H. The class C is the closure of planar triangulated graphs under taking of contractions. In fact, we prove that a graph H ∈ C if and only if there exists a constant c H such that if the treewidth of a graph is at least c H , it contains H as a contraction. We also provide a characterization of C in terms of minimal forbidden contractions.
  • Idioma: Inglês

Buscando em bases de dados remotas. Favor aguardar.