Arnborg (1985) e robertson/seymour (1986) introduziram, de modo independente, um conceito que se mostra uma boa medida da complexidade de um grafo g: dimensao de g (arnborg) ou tree-width de g (robertson, seymour). O primeiro autor apresenta um paradigma para desenvolver algoritmos polinomias, quando restritos a grafos com dimensao limitada para diversos problemas np-dificeis. Os outros utilizam o conceito de tree-width para resolver a conjectura well-quasi-ordering de k. Wagner e apresentar um algoritmo polinomial para o problema dos k caminhos disjuntos. O conceito de tree-width foi aproveitado por bodlander para paralelizar o paradigma de arnborg e mostrar que varios problemas np-dificeis, quando restritos a grafos com tree-width limitada, estao na classe nc. Neste trabalho apresentamos o paradigma de arnborg, generalizado e melhor formalizado, juntamente com sua aplicacao a quatro problemas np-completos, rigorosamente analisados: conjunto estavel maximo, clique maximo, coloracao minima e circuito hamiltoniano. Em seguida fazemos uma demonstracao construtiva (original) da equivalencia entre dimensao e tree-width de um grafo. Por ultimo, estudamos o problema de se determinar a dimensao (tree-width) de um dado grafo e apresentamos algumas classes de grafos com dimensao (tree-width) limitada

not available