A LAYER-DECOMPOSITION WITH DEGREE METHOD FOR SUBGRAPHS RECOGNITION PROBLEM
Yifan Xu · 2003
Abstract. For two planar undirected graphs G and H, the subgraphs recognition problem (SRP) is to find and list all subgraphs of G which are isomorphic to H. In this paper, we introduce the idea of layerdecomposition with degree and present an algorithm based on this idea for SRP. Since subgraphs isomorphic to each other contain their spanning trees with the same decomposition, the SRP can be decomposed into two subproblems: First, find subtrees of G which have the same layerdecomposition as that of H. Then, test whether the induced subgraphs generated by these subtrees are isomorphic to H. By this scheme, we greatly decrease the complexity to O(n( ∆ − 1) k−1 k 2), where ∆ is the degree of G and n, k are the orders of G, H respectively. 1.