Esta tese está dividida em duas partes. A primeira é um estudo do empacotamento de duas árvores de Steiner, que é um problema NP-difícil com aplicações em projeto de circuitos VLSI. É proposta uma nova formulação e a partir de um estudo teórico dos poliedros associados, novas classes de desigualdades definindo facetas são encontradas. Isso resulta em um algoritmo de branch-and-cut para o problema. É feito um detalhado estudo de técnicas práticas para acelerar esse algoritmo. O código resultante consegue um desempenho muito bom, resolvendo instâncias com 10.000 vértices em alguns minutos. A segunda parte da tese trata do problema de Steiner em grafos, também NP-difícil. A fase de pré-processamento é uma das técnicas decisivas na resolução de grandes instâncias desse problema. Entretanto, nas instâncias originadas de projeto de circuitos VLSI, uma das mais importante aplicações do problema de Steiner, as técnicas de pré-processamento tradicionais não funcionam bem. Propomos novos testes de redução particularmente adequados a esses casos. Testando o procedimento resultante em instâncias reais disponíveis na internet, obtivemos significativas reduções. Finalmente, estudamos a resolução exata do problema de Steiner em grafos. Analisamos o comportamento de uma conhecida heurística dual para esse problema e propomos três novas heurísticas duais para melhorar o seu desempenho. Essas heurísticas levam a dois algoritmos exatos, um branch-and-bound que não usa programação linear e um branch-and-cut. Esses algoritmos foram testados em um variado conjunto  de instâncias da literatura e obtiveram bons resultados, resolvendo várias dessas instâncias pela primeira vez.