{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,7]],"date-time":"2026-03-07T02:18:37Z","timestamp":1772849917450,"version":"3.50.1"},"reference-count":63,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2012,10,1]],"date-time":"2012-10-01T00:00:00Z","timestamp":1349049600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2012,10]]},"abstract":"<jats:p>We give a logical characterization of the polynomial-time properties of graphs embeddable in some surface. For every surface<jats:italic>S<\/jats:italic>, a property P of graphs embeddable in<jats:italic>S<\/jats:italic>is decidable in polynomial time if and only if it is definable in fixed-point logic with counting. It is a consequence of this result that for every surface<jats:italic>S<\/jats:italic>there is a<jats:italic>k<\/jats:italic>such that a simple combinatorial algorithm, namely \u201cthe<jats:italic>k<\/jats:italic>-dimensional Weisfeiler-Lehman algorithm\u201d, decides isomorphism of graphs embeddable in<jats:italic>S<\/jats:italic>in polynomial time.<\/jats:p><jats:p>We also present (without proof) generalizations of these results to arbitrary classes of graphs with excluded minors.<\/jats:p>","DOI":"10.1145\/2371656.2371662","type":"journal-article","created":{"date-parts":[[2012,11,13]],"date-time":"2012-11-13T15:03:58Z","timestamp":1352819038000},"page":"1-64","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":30,"title":["Fixed-point definability and polynomial time on graphs with excluded minors"],"prefix":"10.1145","volume":"59","author":[{"given":"Martin","family":"Grohe","sequence":"first","affiliation":[{"name":"Humboldt University Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,11,5]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/647890.739270"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/0209047"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/800061.808746"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-0072(99)00005-6"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1190150152"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(90)90013-5"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01305232"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(82)90012-5"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190070410"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(99)00184-5"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2009.24"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.14"},{"key":"e_1_2_2_13_1","unstructured":"Diestel R. 2005. Graph Theory 3rd Ed. Springer. Diestel R. 2005. Graph Theory 3rd Ed. Springer."},{"key":"e_1_2_2_14_1","unstructured":"Ebbinghaus H.-D. and Flum J. 1999. Finite Model Theory 2nd Ed. Springer. Ebbinghaus H.-D. and Flum J. 1999. Finite Model Theory 2nd Ed. Springer."},{"key":"e_1_2_2_15_1","doi-asserted-by":"crossref","unstructured":"Ebbinghaus H.-D. Flum J. and Thomas W. 1994. Mathematical Logic 2nd Ed. Springer. Ebbinghaus H.-D. Flum J. and Thomas W. 1994. Mathematical Logic 2nd Ed. Springer.","DOI":"10.1007\/978-1-4757-2355-7"},{"key":"e_1_2_2_16_1","volume-title":"SIAM-AMS Proceedings on Complexity of Computation.","volume":"7","author":"Fagin R.","year":"1974"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/800141.804671"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.2307\/2586569"},{"key":"e_1_2_2_19_1","unstructured":"Gr\u00e4del E. Kolaitis P. Libkin L. Marx M. Spencer J. Vardi M. Venema Y. and Weinstein S. 2007. Finite Model Theory and Its Applications. Springer. Gr\u00e4del E. Kolaitis P. Libkin L. Marx M. Spencer J. Vardi M. Venema Y. and Weinstein S. 2007. Finite Model Theory and Its Applications. Springer."},{"key":"e_1_2_2_20_1","doi-asserted-by":"crossref","unstructured":"Gr\u00e4del E. and Otto M . 1993 . Inductive definability with counting on finite structures. In Proceedings of the Computer Science Logic 6th Workshop (CSL'92). Selected Papers E. B\u00f6rger G. J\u00e4ger H. K. B\u00fcning S. Martini and M. Richter Eds. Lecture Notes in Computer Science vol. 702 Springer 231--247. Gr\u00e4del E. and Otto M. 1993. Inductive definability with counting on finite structures. In Proceedings of the Computer Science Logic 6th Workshop (CSL'92). Selected Papers E. B\u00f6rger G. J\u00e4ger H. K. B\u00fcning S. Martini and M. Richter Eds. Lecture Notes in Computer Science vol. 702 Springer 231--247.","DOI":"10.1007\/3-540-56992-8_15"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/788020.788896"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335313"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2008.10"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2010.22"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1953122.1953150"},{"key":"e_1_2_2_26_1","unstructured":"Grohe M. 2012. Descriptive complexity canonisation and definable graph structure theory. http:\/\/www2. informatik.hu-berlin.de\/~grohe\/cap. Grohe M. 2012. Descriptive complexity canonisation and definable graph structure theory. http:\/\/www2. informatik.hu-berlin.de\/~grohe\/cap."},{"key":"e_1_2_2_27_1","doi-asserted-by":"crossref","unstructured":"Grohe M. and Mari\u00f1o J . 1999 . Definability and descriptive complexity on databases of bounded tree-width. In Proceedings of the 7th International Conference on Database Theory. C. Beeri and P. Buneman Eds. Lecture Notes in Computer Science vol. 1540 Springer 70--82. Grohe M. and Mari\u00f1o J. 1999. Definability and descriptive complexity on databases of bounded tree-width. In Proceedings of the 7th International Conference on Database Theory. C. Beeri and P. Buneman Eds. Lecture Notes in Computer Science vol. 1540 Springer 70--82.","DOI":"10.1007\/3-540-49257-7_6"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/11786986_2"},{"key":"e_1_2_2_29_1","unstructured":"Gross J. and Tucker T. 1987. Topological Graph Theory. Wiley. Gross J. and Tucker T. 1987. Topological Graph Theory. Wiley."},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0099486"},{"key":"e_1_2_2_31_1","volume-title":"Current Trends in Theoretical Computer Science","author":"Gurevich Y."},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(86)90055-2"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.2307\/421173"},{"key":"e_1_2_2_34_1","doi-asserted-by":"crossref","unstructured":"Hopcroft J. and Tarjan R. 1972. Isomorphism of planar graphs (working paper). In Complexity of Computer Computations R. E. Miller and J. W. Thatcher Eds. Plenum Press. Hopcroft J. and Tarjan R. 1972. Isomorphism of planar graphs (working paper). In Complexity of Computer Computations R. E. Miller and J. W. Thatcher Eds. Plenum Press.","DOI":"10.1007\/978-1-4684-2001-2_13"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/800119.803896"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/800070.802187"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(86)80029-8"},{"key":"e_1_2_2_38_1","volume-title":"Proceedings of the 2nd IEEE Symposium on Structure in Complexity Theory. 194--202","author":"Immerman N.","year":"1987"},{"key":"e_1_2_2_39_1","doi-asserted-by":"crossref","unstructured":"Immerman N. 1999. Descriptive Complexity. Springer. Immerman N. 1999. Descriptive Complexity. Springer.","DOI":"10.1007\/978-1-4612-0539-5"},{"key":"e_1_2_2_40_1","doi-asserted-by":"crossref","unstructured":"Immerman N. and Lander E. 1990. Describing graphs: A first-order approach to graph canonization. In Complexity Theory Retrospective A. Selman Ed. Springer 59--81. Immerman N. and Lander E. 1990. Describing graphs: A first-order approach to graph canonization. In Complexity Theory Retrospective A. Selman Ed. Springer 59--81.","DOI":"10.1007\/978-1-4612-4478-3_5"},{"key":"e_1_2_2_41_1","doi-asserted-by":"crossref","unstructured":"K\u00f6bler J. and Verbitsky O . 2008 . From invariants to canonization in parallel. In Proceedings of the 3rd International Computer Science Symposium. E. Hirsch A. Razborov A. Semenov and A. Slissenko Eds. Lecture Notes in Computer Science vol. 5010 Springer 216--227. K\u00f6bler J. and Verbitsky O. 2008. From invariants to canonization in parallel. In Proceedings of the 3rd International Computer Science Symposium. E. Hirsch A. Razborov A. Semenov and A. Slissenko Eds. Lecture Notes in Computer Science vol. 5010 Springer 216--227.","DOI":"10.1007\/978-3-540-79709-8_23"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.5555\/645683.664571"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2010.42"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1963-0157364-3"},{"key":"e_1_2_2_45_1","doi-asserted-by":"crossref","unstructured":"Libkin L. 2004. Elements of Finite Model Theory. Springer. Libkin L. 2004. Elements of Finite Model Theory. Springer.","DOI":"10.1007\/978-3-662-07003-1"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(82)90009-5"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(83)80048-5"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/800141.804670"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1137\/S089548019529248X"},{"key":"e_1_2_2_50_1","doi-asserted-by":"crossref","unstructured":"Mohar B. and Thomassen C. 2001. Graphs on Surfaces. Johns Hopkins University Press. Mohar B. and Thomassen C. 2001. Graphs on Surfaces. Johns Hopkins University Press.","DOI":"10.56021\/9780801866890"},{"key":"e_1_2_2_51_1","volume-title":"Lecture Notes in Logic","volume":"9","author":"Otto M.","year":"1997"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2005.10.006"},{"key":"e_1_2_2_53_1","first-page":"147","article-title":"The isomorphism problem for classes of graphs that are invariant with respect to contraction","volume":"3","author":"Ponomarenko I. N.","year":"1988","journal-title":"Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. 174, Teor. Slozhn. Vychisl."},{"key":"e_1_2_2_54_1","doi-asserted-by":"crossref","unstructured":"Ringel G. 1974. Map Color Theorem. Springer. Ringel G. 1974. Map Color Theorem. Springer.","DOI":"10.1007\/978-3-642-65759-7"},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(91)90061-N"},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1995.1006"},{"key":"e_1_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1999.1919"},{"key":"e_1_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2004.08.001"},{"key":"e_1_2_2_59_1","unstructured":"Robertson N. and Vitray R. 1990. Representativity of surface embeddings. In Paths Flows and VLSI-Layout B. Korte L. Lov\u00e1sz H. Pr\u00f6mel and A. Schrijver Eds. Springer 293--328. Robertson N. and Vitray R. 1990. Representativity of surface embeddings. In Paths Flows and VLSI-Layout B. Korte L. Lov\u00e1sz H. Pr\u00f6mel and A. Schrijver Eds. Springer 293--328."},{"key":"e_1_2_2_60_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(89)90006-0"},{"key":"e_1_2_2_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/800070.802186"},{"key":"e_1_2_2_62_1","doi-asserted-by":"publisher","DOI":"10.5555\/1763424.1763505"},{"key":"e_1_2_2_63_1","doi-asserted-by":"publisher","DOI":"10.2307\/2371086"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2371656.2371662","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2371656.2371662","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T09:21:18Z","timestamp":1750238478000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2371656.2371662"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,10]]},"references-count":63,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2012,10]]}},"alternative-id":["10.1145\/2371656.2371662"],"URL":"https:\/\/doi.org\/10.1145\/2371656.2371662","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,10]]},"assertion":[{"value":"2011-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-11-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}