Dorn, Frederic
Planar Subgraph Isomorphism Revisited
Abstract
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'GAA 99] gives the first linear time algorithm for subgraph isomorphism for a fixedsize pattern, say of order $k$, and arbitrary planar host graph, improving upon the $O(n^{\sqrt{k}})$time algorithm when using the ``Colorcoding'' technique of Alon et al [J'ACM 95]. Eppstein's 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'' 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).
BibTeX  Entry
@InProceedings{dorn:LIPIcs:2010:2460,
author = {Frederic Dorn},
title = {{Planar Subgraph Isomorphism Revisited}},
booktitle = {27th International Symposium on Theoretical Aspects of Computer Science},
pages = {263274},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897163},
ISSN = {18688969},
year = {2010},
volume = {5},
editor = {JeanYves Marion and Thomas Schwentick},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2010/2460},
URN = {urn:nbn:de:0030drops24605},
doi = {http://dx.doi.org/10.4230/LIPIcs.STACS.2010.2460},
annote = {Keywords: Graph algorithms, Subgraph Isomorphism, NPhard problems, Dynamic programming, Topological graph theory}
}
Keywords: 

Graph algorithms, Subgraph Isomorphism, NPhard problems, Dynamic programming, Topological graph theory 
Seminar: 

27th International Symposium on Theoretical Aspects of Computer Science

Issue date: 

2010 
Date of publication: 

09.03.2010 