{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T17:38:54Z","timestamp":1773250734901,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":72,"publisher":"ACM","license":[{"start":{"date-parts":[[2008,5,17]],"date-time":"2008-05-17T00:00:00Z","timestamp":1210982400000},"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":[],"published-print":{"date-parts":[[2008,5,17]]},"DOI":"10.1145\/1374376.1374443","type":"proceedings-article","created":{"date-parts":[[2008,5,28]],"date-time":"2008-05-28T16:50:20Z","timestamp":1211993420000},"page":"471-480","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":16,"title":["Graph and map isomorphism and all polyhedral embeddings in linear time"],"prefix":"10.1145","author":[{"given":"Ken-ichi","family":"Kawarabayashi","sequence":"first","affiliation":[{"name":"National Institute of Informatics, Tokyo, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bojan","family":"Mohar","sequence":"additional","affiliation":[{"name":"Simon Fraser University, Burnaby, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,5,17]]},"reference":[{"key":"e_1_3_2_1_1_1","first-page":"641","volume-title":"Proc. 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'08)","author":"Adler I.","year":"2008","unstructured":"I. Adler , M. Grohe and S. Kreutzer , Computing excluded minors , Proc. 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'08) ,pp. 641 -- 650 , 2008 . I. Adler, M. Grohe and S. Kreutzer, Computing excluded minors, Proc. 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'08),pp. 641--650, 2008."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(92)90064-5"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(89)90031-0"},{"key":"e_1_3_2_1_4_1","first-page":"79","article-title":"Carlo algorithms in graph isomorphism testing","author":"Babai L.","year":"1979","unstructured":"L. Babai , Monte Carlo algorithms in graph isomorphism testing , Univ. Montreal Tech. Rep. DMS 79 - 10 , 1979 . http:\/\/people.cs.uchicago.edu\/laci\/lasvegas79.pdf L. Babai, Monte Carlo algorithms in graph isomorphism testing, Univ. Montreal Tech. Rep. DMS 79-10, 1979. http:\/\/people.cs.uchicago.edu\/laci\/lasvegas79.pdf","journal-title":"Univ. Montreal Tech. Rep. DMS"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/0209047"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/800070.802206"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1979.8"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90028-1"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(90)90013-5"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793251219"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1999.1939"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(76)80045-1"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(87)90232-8"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.2307\/1968030"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-006-1292-5"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480191196769"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00273-3"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90004-2"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/103418.103456"},{"key":"e_1_3_2_1_20_1","volume-title":"Graph Theory","author":"Diestel R.","year":"2005","unstructured":"R. Diestel , Graph Theory , 3 rd Edition, Springer , 2005 . R. Diestel, Graph Theory, 3rd Edition, Springer, 2005.","edition":"3"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1998.1862"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/513400.513430"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/800135.804395"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/800141.804671"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(84)90019-1"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/116825.116852"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/12130.12137"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335313"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/11786986_2"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/800119.803896"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/0202012"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_13"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(73)80013-3"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/321850.321852"},{"key":"e_1_3_2_1_35_1","first-page":"85","article-title":"Elimination of local bridges","volume":"47","author":"Juvan M.","year":"1997","unstructured":"M. Juvan , J. Marin\u010dek , and B. Mohar , Elimination of local bridges , Math. Slovaca 47 ( 1997 ), 85 -- 92 . M. Juvan, J. Marin\u010dek, and B. Mohar, Elimination of local bridges, Math. Slovaca 47 (1997),85--92.","journal-title":"Math. Slovaca"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-006-0684-x"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250848"},{"key":"e_1_3_2_1_38_1","unstructured":"K. Kawarabayashi B. Mohar and B. Reed A simpler linear time algorithm for embedding graphs into anarbitrary surface in preparation. K. Kawarabayashi B. Mohar and B. Reed A simpler linear time algorithm for embedding graphs into anarbitrary surface in preparation."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/378583.378630"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/800141.804669"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/0136016"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/0209046"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(82)90009-5"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(83)80048-5"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(83)80047-3"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/800141.804670"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01192526"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237986"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1137\/S089548019529248X"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930100003"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.2001.2036"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"crossref","DOI":"10.56021\/9780801866890","volume-title":"Graphs on Surfaces","author":"Mohar B.","year":"2001","unstructured":"B. Mohar and C. Thomassen , Graphs on Surfaces , Johns HopkinsUniversity Press , Baltimore, MD , 2001 . B. Mohar and C. Thomassen, Graphs on Surfaces, Johns HopkinsUniversity Press, Baltimore, MD, 2001."},{"key":"e_1_3_2_1_53_1","volume-title":"Zap. Nauchen. Sem. Leningrad.Osdel. Mat. Inst. Steklov. (LOMI) 174, 147--177","author":"Ponomarenko I. N.","year":"1988","unstructured":"I. N. Ponomarenko , The isomorphism problem for classes of graphs that are invariantwith respect to contraction , Zap. Nauchen. Sem. Leningrad.Osdel. Mat. Inst. Steklov. (LOMI) 174, 147--177 , ( 1988 ), inRussian. I. N. Ponomarenko, The isomorphism problem for classes of graphs that are invariantwith respect to contraction, Zap. Nauchen. Sem. Leningrad.Osdel. Mat. Inst. Steklov. (LOMI) 174, 147--177, (1988), inRussian."},{"key":"e_1_3_2_1_54_1","first-page":"552","article-title":"The isomorphism problem for classes of graphs","volume":"304","author":"Ponomarenko I. N.","year":"1989","unstructured":"I. N. Ponomarenko , The isomorphism problem for classes of graphs , Dokl. Akad. Nauk SSSR 304 ( 1989 ) 552 -- 556 ;Engl. transl. in Soviet Math. Dokl. 39 (1989) 119--122. I. N. Ponomarenko, The isomorphism problem for classes of graphs, Dokl. Akad. Nauk SSSR 304 (1989) 552--556;Engl. transl. in Soviet Math. Dokl. 39 (1989) 119--122.","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"e_1_3_2_1_55_1","first-page":"87","volume-title":"Tree width and tangles: a new connectivity measure and someapplications, in \"Surveys in Combinatorics","author":"Reed B.","year":"1997","unstructured":"B. Reed , Tree width and tangles: a new connectivity measure and someapplications, in \"Surveys in Combinatorics , 1997 (London)\", London Math. Soc. Lecture Note Ser. 241, Cambridge Univ. Press , Cambridge, 1997, pp. 87 -- 162 . B. Reed, Tree width and tangles: a new connectivity measure and someapplications, in \"Surveys in Combinatorics, 1997 (London)\", London Math. Soc. Lecture Note Ser. 241, Cambridge Univ. Press, Cambridge, 1997, pp. 87--162."},{"key":"e_1_3_2_1_56_1","first-page":"147","volume-title":"WA, 1991), 295--301","author":"Reed B.","year":"1993","unstructured":"B. Reed , N. Robertson , A. Schrijver and P. D. Seymour , Finding disjoint trees in planar graphs in linear time, in Graph Structure Theory (Seattle , WA, 1991), 295--301 ,%Contemp. Math. 147 ,Amer. Math. Soc. , 1993 . B. Reed, N. Robertson, A. Schrijver and P. D. Seymour,Finding disjoint trees in planar graphs in linear time, in Graph Structure Theory (Seattle, WA, 1991), 295--301,%Contemp. Math. 147,Amer. Math. Soc., 1993."},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)00104-L"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(86)90030-4"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(88)90070-6"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1995.1006"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(03)00042-X"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2004.08.001"},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1994.1073"},{"key":"e_1_3_2_1_64_1","first-page":"293","volume-title":"Springer-Verlag","author":"Robertson N.","year":"1990","unstructured":"N. Robertson , R. P. Vitray, Representativity of surface embeddings,in: \"Paths, Flows, and VLSI-Layout,\"B. Korte, L. Lov\u00e1sz, H. J. Pr\u00f6mel, and A. Schrijver Eds ., Springer-Verlag , Berlin , 1990 , pp. 293 -- 328 . N. Robertson, R. P. Vitray, Representativity of surface embeddings,in: \"Paths, Flows, and VLSI-Layout,\"B. Korte, L. Lov\u00e1sz, H. J. Pr\u00f6mel, and A. Schrijver Eds.,Springer-Verlag, Berlin, 1990, pp. 293--328."},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90010-4"},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0118(199612)23:4%3C337::AID-JGT2%3E3.0.CO;2-S"},{"key":"e_1_3_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(89)90006-0"},{"key":"e_1_3_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1993.1016"},{"key":"e_1_3_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1997.1761"},{"key":"e_1_3_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1145\/98524.98546"},{"key":"e_1_3_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCT.1966.1082573"},{"key":"e_1_3_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1145\/1634.322451"}],"event":{"name":"STOC '08: Symposium on Theory of Computing","location":"Victoria British Columbia Canada","acronym":"STOC '08","sponsor":["ACM Association for Computing Machinery","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the fortieth annual ACM symposium on Theory of computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1374376.1374443","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1374376.1374443","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:57:49Z","timestamp":1750255069000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1374376.1374443"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,5,17]]},"references-count":72,"alternative-id":["10.1145\/1374376.1374443","10.1145\/1374376"],"URL":"https:\/\/doi.org\/10.1145\/1374376.1374443","relation":{},"subject":[],"published":{"date-parts":[[2008,5,17]]},"assertion":[{"value":"2008-05-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}