License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2012.531
URN: urn:nbn:de:0030-drops-34224
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2012/3422/
Go to the corresponding LIPIcs Volume Portal

Bonsma, Paul

Surface Split Decompositions and Subgraph Isomorphism in Graphs on Surfaces

pdf-format:
38.pdf (0.5 MB)

Abstract

The Subgraph Isomorphism problem asks, given a host graph G on n vertices and a pattern graph P on k vertices, whether G contains a subgraph isomorphic to P. The restriction of this problem to planar graphs has often been considered. After a sequence of improvements, the current best algorithm for planar graphs is a linear time algorithm by Dorn (STACS '10), with complexity 2^{O(k)} O(n).
We generalize this result, by giving an algorithm of the same complexity for graphs that can be embedded in surfaces of bounded genus. In addition, we simplify the algorithm and analysis. The key to these improvements is the introduction of surface split decompositions for bounded genus graphs, which generalize sphere cut decompositions for planar graphs. We extend the algorithm for the problem of counting and generating all subgraphs isomorphic to P, even for the case where P is disconnected. This answers an open question by Eppstein (JGAA '99).

BibTeX - Entry

@InProceedings{bonsma:LIPIcs:2012:3422,
  author =	{Paul Bonsma},
  title =	{{Surface Split Decompositions and Subgraph Isomorphism in Graphs on Surfaces}},
  booktitle =	{29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
  pages =	{531--542},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-35-4},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{14},
  editor =	{Christoph D{\"u}rr and Thomas Wilke},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2012/3422},
  URN =		{urn:nbn:de:0030-drops-34224},
  doi =		{10.4230/LIPIcs.STACS.2012.531},
  annote =	{Keywords: Analysis of algorithms, parameterized algorithms, graphs on surfaces, subgraph isomorphism, dynamic programming, branch decompositions, counting probl}
}

Keywords: Analysis of algorithms, parameterized algorithms, graphs on surfaces, subgraph isomorphism, dynamic programming, branch decompositions, counting probl
Collection: 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)
Issue Date: 2012
Date of publication: 24.02.2012

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI