{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,15]],"date-time":"2026-10-15T13:34:36Z","timestamp":1792071276769,"version":"4.4.0"},"reference-count":34,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2015,1]]},"abstract":"<jats:p>We generalize the structure theorem of Robertson and Seymour for graphs excluding a fixed graph $H$ as a minor to graphs excluding $H$ as a topological subgraph. We prove that for a fixed $H$, every graph excluding $H$ as a topological subgraph has a tree decomposition where each part is either \u201calmost embeddable\u201d to a fixed surface or has bounded degree with the exception of a bounded number of vertices. Furthermore, we prove that such a decomposition is computable by an algorithm that is fixed-parameter tractable with parameter $|H|$. We present two algorithmic applications of our structure theorem. To illustrate the mechanics of a \u201ctypical\u201d application of the structure theorem, we show that on graphs excluding $H$ as a topological subgraph, Partial Dominating Set (find $k$ vertices whose closed neighborhood has maximum size) can be solved in time $f(H,k)\\cdot n^{O(1)}$. More significantly, we show that on graphs excluding $H$ as a topological subgraph, Graph Isomorphism can be solved in time $n^{f(H)}$. This result unifies and generalizes two previously known important polynomial time solvable cases of Graph Isomorphism: bounded-degree graphs [E. M. Luks, J. Comput. System Sci., 25 (1982), pp. 42--65] and $H$-minor free graphs [I. N. Ponomarenko, Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI), 174 (1988), pp. 147--177, 182]. The proof of this result needs a generalization of our structure theorem to the context of invariant treelike decomposition.<\/jats:p>","DOI":"10.1137\/120892234","type":"journal-article","created":{"date-parts":[[2015,2,18]],"date-time":"2015-02-18T13:38:08Z","timestamp":1424266688000},"page":"114-159","source":"Crossref","is-referenced-by-count":51,"title":["Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs"],"prefix":"10.1137","volume":"44","author":[{"given":"Martin","family":"Grohe","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"D\u00e1niel","family":"Marx","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2015,2,18]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.12.002"},{"key":"atypb2","doi-asserted-by":"crossref","unstructured":"L. Babai and E. M. Luks,\n                      Canonical labeling of graphs\n                      , in Proceedings of the 15th ACM Symposium on Theory of Computing, 1983, pp. 171-183.","DOI":"10.1145\/800061.808746"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(90)90013-5"},{"key":"atypb4","doi-asserted-by":"crossref","unstructured":"C. Chekuri, S. Khanna, and F. B. Shepherd,\n                      Edge-disjoint paths in planar graphs\n                      , in Proceedings of the 45th Symposium on Foundations of Computer Science, 2004, pp. 71-80.","DOI":"10.1109\/FOCS.2004.27"},{"key":"atypb5","doi-asserted-by":"crossref","unstructured":"E. D. Demaine, M. Hajiaghayi, and K. Kawarabayashi,\n                      Contraction decomposition in $H$-minor-free graphs and algorithmic applications\n                      , in Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011, pp. 441-450.","DOI":"10.1145\/1993636.1993696"},{"key":"atypb6","doi-asserted-by":"crossref","unstructured":"E. D. Demaine, M. T. Hajiaghayi, and K. Kawarabayashi,\n                      Algorithmic graph minor theory: Decomposition, approximation, and coloring\n                      , in Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, 2005, pp. 637-646.","DOI":"10.1109\/SFCS.2005.14"},{"key":"atypb7","unstructured":"F. Dorn, F. V. Fomin, and D. M. Thilikos,\n                      Catalan structures and dynamic programming in H-minor-free graphs\n                      , in Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms, 2008, pp. 631-640."},{"key":"atypb8","doi-asserted-by":"crossref","unstructured":"Z. Dvorak, D. Kr\u00e1l, and R. Thomas,\n                      Deciding first-order properties for sparse graphs\n                      , in Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2010, pp. 133-142.","DOI":"10.1109\/FOCS.2010.20"},{"key":"atypb9","doi-asserted-by":"crossref","unstructured":"I. S. Filotti and J. N. Mayer,\n                      A polynomial-time algorithm for determining the isomorphism of graphs of fixed genus\n                      , in Proceedings of the 12th ACM Symposium on Theory of Computing, 1980, pp. 236-243.","DOI":"10.1145\/800141.804671"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-003-0037-9"},{"key":"atypb12","first-page":"406","author":"Grohe M.","year":"2008","journal-title":"Computer Science"},{"key":"atypb13","first-page":"59","author":"Grohe M.","year":"2012","journal-title":"J. ACM"},{"key":"atypb14","doi-asserted-by":"crossref","unstructured":"M. Grohe, K. Kawarabayashi, D. Marx, and P. Wollan,\n                      Finding topological subgraphs is fixed-parameter tractable\n                      , in Proceedings of the 43nd ACM Symposium on Theory of Computing, 2011, pp. 479-488.","DOI":"10.1145\/1993636.1993700"},{"key":"atypb15","doi-asserted-by":"crossref","unstructured":"M. Grohe, K. Kawarabayashi, and B. Reed,\n                      A simple algorithm for the graph minor decomposition-logic meets structural graph theory\n                      , in Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, 2013, pp. 414-431.","DOI":"10.1137\/1.9781611973105.30"},{"key":"atypb16","doi-asserted-by":"crossref","unstructured":"K. Kawarabayashi, E. D. Demaine, and M. Hajiaghayi,\n                      Additive approximation algorithms for list-coloring minor-closed class of graphs\n                      , in Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms, 2009, pp. 1166-1175.","DOI":"10.1137\/1.9781611973068.126"},{"key":"atypb17","doi-asserted-by":"crossref","unstructured":"K. Kawarabayashi and B. Mohar,\n                      Approximating the list-chromatic number and the chromatic number in minor-closed and odd-minor-closed classes of graphs\n                      , in Proceedings of the 38th ACM Symposium on Theory of Computing, 2006, pp. 401-416.","DOI":"10.1145\/1132516.1132576"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-006-0684-x"},{"key":"atypb19","doi-asserted-by":"crossref","unstructured":"K. Kawarabayashi and P. Wollan,\n                      A shorter proof of the graph minor algorithm: The unique linkage theorem\n                      , in Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010, pp. 687-694.","DOI":"10.1145\/1806689.1806784"},{"key":"atypb20","doi-asserted-by":"crossref","unstructured":"K. Kawarabayashi and P. Wollan,\n                      A simpler algorithm and shorter proof for the graph minor decomposition\n                      , in Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011, pp. 451-458.","DOI":"10.1145\/1993636.1993697"},{"key":"atypb21","first-page":"58","author":"Kneis J.","year":"2006","journal-title":"New York"},{"key":"atypb22","doi-asserted-by":"crossref","unstructured":"D. Lokshtanov, M. Pilipczuk, M. Pilipczuk, and S. Saurabh,\n                      Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth\n                      , CoRR, abs\/1404.0818, 2014.","DOI":"10.1109\/FOCS.2014.28"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(82)90009-5"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1007\/BF01364272"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.10.007"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(83)80047-3"},{"key":"atypb27","doi-asserted-by":"crossref","unstructured":"G. L. Miller,\n                      Isomorphism testing for graphs of bounded genus\n                      , in Proceedings of the 12th ACM Symposium on Theory of Computing, 1980, pp. 225-235.","DOI":"10.1145\/800141.804670"},{"key":"atypb28","unstructured":"I. N. Ponomarenko,\n                      The isomorphism problem for classes of graphs that are invariant with respect to contraction\n                      (in Russian), Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI), 174 (1988), pp. 147-177, 182."},{"key":"atypb29","first-page":"87","author":"Reed B.","year":"1997","journal-title":"UK"},{"key":"atypb30","first-page":"85","author":"Reed B. A.","year":"2003","journal-title":"New York"},{"key":"atypb31","first-page":"153","author":"Robertson N.","year":"1985","journal-title":"UK"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(91)90061-N"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1995.1006"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1999.1898"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2004.08.001"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/120892234","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:16:32Z","timestamp":1787336192000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/120892234"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1]]},"references-count":34,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["10.1137\/120892234"],"URL":"https:\/\/doi.org\/10.1137\/120892234","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1]]}}}