When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2010.2460
URN: urn:nbn:de:0030-drops-24605
URL: http://drops.dagstuhl.de/opus/volltexte/2010/2460/
 Go to the corresponding LIPIcs Volume Portal

Planar Subgraph Isomorphism Revisited

 pdf-format:

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 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'' 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 =	{263--274},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-939897-16-3},
ISSN =	{1868-8969},
year =	{2010},
volume =	{5},
editor =	{Jean-Yves Marion and Thomas Schwentick},
publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},