Campus Event Calendar
Event Entry
What and Who
Surface Split Decompositions and Subgraph Isomorphism in Graphs on Surfaces
Paul Bonsma
HU Berlin
AG1 Mittagsseminar (own work)
AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Friday, 13 April 2012
13:00
30 Minutes
E1 4
024
Saarbrücken
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).
Contact
Matthias Mnich
--email hidden
passcode not visible
logged in users only
Matthias Mnich, 04/10/2012 13:11 -- Created document.