Planar Subgraph Isomorphism Revisited

The problem of {sc Subgraph Isomorphism} is defined as follows: Given a emph{pattern} $H$ and a emph{host graph} $G$ on $n$ vertices, does $G$ contain a subgraph that is isomorphic to $H$? Eppstein [SODA 95, J\u27GAA 99] gives the first linear time algorithm for subgraph isomorphism for a fixed-size pattern, say of order $k$, and arbitrary planar host graph, improving upon the $O(n^{sqrt{k}})$-time algorithm when using the ``Color-coding\u27\u27 technique of Alon et al [J\u27ACM 95]. Eppstein\u27s algorithm runs in time $k^{O(k)} n$, that is, the dependency on $k$ is superexponential. We improve the running time to $2^{O(k)} n$, that is, single exponential in $k$ while keeping the term in $n$ linear. Next to deciding subgraph isomorphism, we can construct a solution and count all solutions in the same asymptotic running time. We may enumerate $omega$ subgraphs with an additive term $O(omega k)$ in the running time of our algorithm. We introduce the technique of ``embedded dynamic programming\u27\u27 on a suitably structured graph decomposition, which exploits the number and topology of the underlying drawings of the subgraph pattern (rather than of the host graph)