Embeddings of image-connected graphs of pathwidth image Original Research Article

We present image embedding algorithms (subgraph isomorphism and its generalizations) for classes of graphs of bounded pathwidth, where n is the number of vertices in the graph. These include the first polynomial-time algorithm for minor containment and the first image algorithm (c a constant independent of k) for topological embedding of graphs from subclasses of partial k-trees, as well as an image algorithm for subgraph isomorphism. Of independent interest are structural properties of k-connected graphs of bounded pathwidth on which our algorithms are based. We also describe special cases which reduce to various generalizations of string matching, permitting more efficient solutions. Finally, we describe image algorithms for solving these problems on arbitrary graphs of pathwidth at most k.