Structure theorem and isomorphism test for graphs with excluded topological subgraphs

摘要: We generalize the structure theorem of Robertson and Seymour for graphs excluding a fixed graph H as minor to topological subgraph. prove that H, every subgraph has tree decomposition where each part is either "almost embeddable" surface or bounded degree with exception number vertices. Furthermore, such computable by an algorithm fixed-parameter tractable parameter |H|. present two algorithmic applications our theorem. To illustrate mechanics "typical" application theorem, we show on subgraph, Partial Dominating Set (find k vertices whose closed neighborhood maximum size) can be solved in time f(H,k) • nO(1) time. More significantly, Graph Isomorphism nf(H). This result unifies generalizes previously known important polynomial-time solvable cases Isomorphism: bounded-degree H-minor free graphs. The proof this needs generalization context invariant treelike decomposition.