Surface Split Decompositions and Subgraph Isomorphism in Graphs on Surfaces

Details Surface Split Decompositions and Subgraph Isomorphism in Graphs on Surfaces Surface Split Decompositions and Subgraph Isomorphism in Graphs on Surfaces

2011-09-21

arxiv.org/abs/1109.4554v1

Computer Science

Discrete Mathematics

Scientific paper

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. At the same time, 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 (SODA '95 / JGAA '99).

Affiliated with

Also associated with

No associations

Rating

Surface Split Decompositions and Subgraph Isomorphism in Graphs on Surfaces does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Surface Split Decompositions and Subgraph Isomorphism in Graphs on Surfaces, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Surface Split Decompositions and Subgraph Isomorphism in Graphs on Surfaces will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-257764