We present sequential and parallel algorithms for various embedding problems on bounded degree partial k-trees and k-connected partial k-trees; these include subgraph isomorphism and topological embedding, known to be NP-complete for general partial k-trees. As well as contributing to our understanding of the types of graphs for which these problems are tractable, this paper introduces methods for solving problems on graphs. In particular, we make use of the tree-decomposition of the graph to apply techniques used to solve problems on trees to solve problems on partial k-trees.