Subgraph isomorphism in planar graphs and related problems

David Eppstein

*J. Graph Algorithms & Applications* 3(3):1–27, 1999

*Mathematical Reviews* 2001b:05154, 2001

Reviewed by Paul Klingsberg

The subgraph isomorphism problem is the following. Given a graph $G$ and another graph $H$, one must determine whether $G$ has a subgraph that is isomorphic to $H$. In this fully general form, the problem is NP-complete; but if $H$ is a fixed $l$-vertex graph, as the author points out, this problem can clearly be solved in $O(n\sp l)$ time, where $n$ is the number of vertices of $G$. In the current paper, it is assumed that $G$ and $H$ are planar; and in this case the author develops an algorithm that requires only $O(C\sb Hn)$ time (although the constant $C\sb H$ grows exponentially with $l$---necessarily so, if $\rm P\ne NP$). The main idea behind the algorithm is that of constructing a cover $\{G\sb i\}$ for a planar graph $G$ and providing a so-called "tree decomposition" for each element $G\sb i$ of the cover. (A tree decomposition of a graph $G$ is a tree $T$ with these properties: (1) each node $N$ of $T$ is provided with a label $L(N)\subseteq V(G)$; (2) for each $v\in V(G)$, the set of tree nodes whose labels contain $v$ forms a contiguous subtree of $T$; and (3) for each edge $\{v,w\}$ of $G$, there is at least one node $N$ of $T$ such that both $v$ and $w$ are in $L(N)$.) Specifically, for an $n$-vertex planar graph $G$, the author shows how, for any positive integer $w$, to do the following in $O(w\sp 2n)$ time. He covers $G$ with a collection of subgraphs $\{G\sb i\}$, so that each vertex of $G$ is included in at most $w$ of the $\{G\sb i\}$; he provides for each $G\sb i$ a tree decomposition in which all labels have $\le(3w-2)$ elements; and he partitions $V(G)$ into subsets $\{S\sb i\}$ in such a way that, for any connected $w$-vertex subgraph $H$ of $G$, if $i$ is the smallest value for which $H\cap S\sb i$ is nonempty, then $H$ is a subgraph of $G\sb i$ but is not a subgraph of $G\sb j$ for any $j>i$. The main result, an algorithm for deciding the isomorphism question in linear time, is then based on dynamic programming in the trees associated to the subgraphs $\{G\sb i\}$. The author also uses this technique to construct efficient algorithms for a number of other decision and enumeration problems for planar graphs, including connectivity, diameter, girth, induced subgraph isomorphism, and shortest path.