{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,7]],"date-time":"2026-03-07T09:06:09Z","timestamp":1772874369177,"version":"3.50.1"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2019,11,27]],"date-time":"2019-11-27T00:00:00Z","timestamp":1574812800000},"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":[[2019,12,31]]},"abstract":"<jats:p>We prove that the Weisfeiler--Leman (WL) dimension of the class of all finite planar graphs is at most 3. In particular, every finite planar graph is definable in first-order logic with counting using at most 4 variables. The previously best-known upper bounds for the dimension and number of variables were 14 and 15, respectively.<\/jats:p>\n          <jats:p>First, we show that, for dimension 3 and higher, the WL-algorithm correctly tests isomorphism of graphs in a minor-closed class whenever it determines the orbits of the automorphism group of every arc-colored 3-connected graph belonging to this class.<\/jats:p>\n          <jats:p>Then, we prove that, apart from several exceptional graphs (which have WL-dimension at most 2), the individualization of two appropriately chosen vertices of a colored 3-connected planar graph followed by the one-dimensional WL-algorithm produces the discrete vertex partition. This implies that the three-dimensional WL-algorithm determines the orbits of arc-colored 3-connected planar graphs.<\/jats:p>\n          <jats:p>As a byproduct of the proof, we get a classification of the 3-connected planar graphs with fixing number 3.<\/jats:p>","DOI":"10.1145\/3333003","type":"journal-article","created":{"date-parts":[[2019,11,27]],"date-time":"2019-11-27T13:21:28Z","timestamp":1574860888000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":32,"title":["The Weisfeiler--Leman Dimension of Planar Graphs Is at Most 3"],"prefix":"10.1145","volume":"66","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4614-9444","authenticated-orcid":false,"given":"Sandra","family":"Kiefer","sequence":"first","affiliation":[{"name":"RWTH Aachen University, Ahornstra\u00dfe, Aachen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ilia","family":"Ponomarenko","sequence":"additional","affiliation":[{"name":"St. Petersburg Department of Steklov Mathematical Institute of the Russian Academy of Sciences, Fontanka, St. Petersburg, Russia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pascal","family":"Schweitzer","sequence":"additional","affiliation":[{"name":"University of Kaiserslautern, Postfach, Kaiserslautern, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,11,27]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-22177-9_26"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/120867834"},{"key":"e_1_2_1_3_1","first-page":"1","article-title":"The graph isomorphism problem (Dagstuhl Seminar 15511)","volume":"5","author":"Babai L\u00e1szl\u00f3","year":"2015","unstructured":"L\u00e1szl\u00f3 Babai, Anuj Dawar, Pascal Schweitzer, and Jacobo Tor\u00e1n. 2015. The graph isomorphism problem (Dagstuhl Seminar 15511). Dagstuhl Rep. 5, 12 (2015), 1--17.","journal-title":"Dagstuhl Rep."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933575.2934560"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01305232"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2009.16"},{"key":"e_1_2_1_7_1","volume-title":"Ponomarenko","author":"Evdokimov Sergei","year":"2000","unstructured":"Sergei Evdokimov and Ilia N. Ponomarenko. 2000. Separability number and schurity number of coherent configurations. Electr. J. Combin. 7 (2000)."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.1998.705639"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335313"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2371656.2371662"},{"key":"e_1_2_1_11_1","volume-title":"Tangled up in blue (a survey on connectivity, decompositions, and tangles). CoRR abs\/1605.06704","author":"Grohe Martin","year":"2016","unstructured":"Martin Grohe. 2016. Tangled up in blue (a survey on connectivity, decompositions, and tangles). CoRR abs\/1605.06704 (2016)."},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Martin Grohe. 2017. Descriptive Complexity Canonisation and Definable Graph Structure Theory. Cambridge University Press.","DOI":"10.1017\/9781139028868"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-49257-7_6"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the International Workshop\/Annual Conference of the Computer Science Logic (CSL\u201912)","volume":"16","author":"Grohe Martin","year":"2012","unstructured":"Martin Grohe and Martin Otto. 2012. Pebble games and linear equations. In Proceedings of the International Workshop\/Annual Conference of the Computer Science Logic (CSL\u201912), LIPIcs, Vol. 16. Schloss Dagstuhl--Leibniz-Zentrum f\u00fcr Informatik, 289--304."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/11786986_2"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00232"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(71)90019-6"},{"key":"e_1_2_1_18_1","volume-title":"Hopcroft and Robert Endre Tarjan","author":"John","year":"1972","unstructured":"John E. Hopcroft and Robert Endre Tarjan. 1972. Isomorphism of planar graphs. In Complexity of Computer Computations (The IBM Research Symposia Series). Plenum Press, 131--152."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(73)80013-3"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the Annual ACM Symposium on Theory of Computing (STOC\u201974)","author":"Hopcroft John E.","unstructured":"John E. Hopcroft and J. K. Wong. 1974. Linear time algorithm for isomorphism of planar graphs (preliminary report). In Proceedings of the Annual ACM Symposium on Theory of Computing (STOC\u201974). ACM, 172--184."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1021146226285"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933575.2933595"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48057-1_25"},{"key":"e_1_2_1_24_1","first-page":"17","article-title":"COCO2P: GAP-package for the Computation with Coherent Configurations","volume":"0","author":"Klin Mikhail","year":"2018","unstructured":"Mikhail Klin, Christian Pech, and Sven Reichard. 2018. COCO2P: GAP-package for the Computation with Coherent Configurations, Version 0.17. Retrieved from https:\/\/github.com\/chpech\/COCO2P.","journal-title":"Version"},{"key":"e_1_2_1_25_1","volume-title":"Handbook of Graph Drawing and Visualization","author":"Kobourov Stephen G.","unstructured":"Stephen G. Kobourov. 2013. Force-directed drawing algorithms. In Handbook of Graph Drawing and Visualization. Chapman 8 Hall\/CRC, 383--408."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2013.09.003"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-06686-8_21"},{"key":"e_1_2_1_28_1","volume-title":"Graphs on Surfaces","author":"Mohar Bojan","unstructured":"Bojan Mohar and Carsten Thomassen. 2001. Graphs on Surfaces. Johns Hopkins University Press, Baltimore, MD."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01098279"},{"key":"e_1_2_1_30_1","volume-title":"Defining PTIME Problems on Planar Graphs with Few Variables. Master\u2019s thesis","author":"Redies Joachim","unstructured":"Joachim Redies. 2014. Defining PTIME Problems on Planar Graphs with Few Variables. Master\u2019s thesis. RWTH Aachen University."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s3-13.1.743"},{"key":"e_1_2_1_32_1","series-title":"Lecture Notes in Computer Science","volume-title":"STACS\u201907","author":"Verbitsky Oleg","unstructured":"Oleg Verbitsky. 2007. Planar graphs: Logical complexity and parallel isomorphism tests. In STACS\u201907, Lecture Notes in Computer Science, Vol. 4393. Springer, 682--693."},{"key":"e_1_2_1_33_1","series-title":"Lecture Notes in Mathematics","volume-title":"On Construction and Identification of Graphs","author":"Weisfeiler Boris","unstructured":"Boris Weisfeiler. 1976. On Construction and Identification of Graphs. Lecture Notes in Mathematics, Vol. 558. Springer."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3333003","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3333003","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:57:57Z","timestamp":1750208277000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3333003"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11,27]]},"references-count":33,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2019,12,31]]}},"alternative-id":["10.1145\/3333003"],"URL":"https:\/\/doi.org\/10.1145\/3333003","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,11,27]]},"assertion":[{"value":"2018-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-11-27","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}