Algorithms by layer-decomposition for the subgraph recognition problem with attributes
Yifan Xu · Journal of Industrial and Management Optimization · 2005
Given two planar graphs $G$ and $H$, the subgraph recognition problem (SRP)is concerned with finding all isomorphic subgraphs of $H$ in $G$. Using the idea oflayer-decomposition, we develop algorithms for SRP that have computational complexity$O(n(\Delta-1)^{k-1})$, where $\Delta$ is the degree of $G$ and $n, k$ are the orders of $G, H$respectively.