{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,9]],"date-time":"2026-03-09T21:35:12Z","timestamp":1773092112724,"version":"3.50.1"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2024,11,22]],"date-time":"2024-11-22T00:00:00Z","timestamp":1732233600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"JSPS Kakenhi","award":["22H05001"],"award-info":[{"award-number":["22H05001"]}]},{"name":"JSPS Kakenhi","award":["JP20A402"],"award-info":[{"award-number":["JP20A402"]}]},{"name":"JST ASPIRE","award":["JPMJAP2302"],"award-info":[{"award-number":["JPMJAP2302"]}]},{"name":"NSERC Discovery","award":["R611450"],"award-info":[{"award-number":["R611450"]}]},{"DOI":"10.13039\/501100005357","name":"Slovak Research and Development Agency","doi-asserted-by":"crossref","award":["APVV-19-0308"],"award-info":[{"award-number":["APVV-19-0308"]}],"id":[{"id":"10.13039\/501100005357","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001824","name":"GA\u010cR","doi-asserted-by":"crossref","award":["20-15576S"],"award-info":[{"award-number":["20-15576S"]}],"id":[{"id":"10.13039\/501100001824","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Carlsberg Foundation Young Researcher Fellowship","award":["CF21-0682"],"award-info":[{"award-number":["CF21-0682"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2025,1,31]]},"abstract":"<jats:p>\n            A map is a\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(2\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            -cell decomposition of a closed compact surface, i.e., an embedding of a graph such that every face is homeomorphic to an open disc. An automorphism of a map can be thought of as a permutation of the vertices, which preserves the vertex-edge-face incidences in the embedding. Every automorphism of a map determines an angle-preserving homeomorphism of the surface. While it is conjectured that there is no \u201ctruly subquadratic\u201d algorithm for testing map isomorphism for unconstrained genus, we present a linear-time algorithm for computing the generators of the automorphism group of a map on an orientable surface of genus\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(g\\neq 0\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            , parametrized by the genus\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(g\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            . A map on an orientable surface is uniform if the cyclic vector of sizes of faces incident to a vertex\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(v\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            does not depend on the choice of\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(v\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            . The algorithm applies a sequence of local reductions and produces a uniform map while preserving the automorphism group. The automorphism group of the original map can be reconstructed from the automorphism group of the associated uniform map in linear time. We also extend the algorithm to non-orientable surfaces by making use of the antipodal double-cover. The algorithm can be used to solve the map isomorphism problem between maps (orientable or non-orientable) of bounded negative Euler characteristic.\n          <\/jats:p>","DOI":"10.1145\/3686798","type":"journal-article","created":{"date-parts":[[2024,8,7]],"date-time":"2024-08-07T15:35:32Z","timestamp":1723044932000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Automorphisms and Isomorphisms of Maps in Linear Time"],"prefix":"10.1145","volume":"21","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6056-4287","authenticated-orcid":false,"given":"Ken-ichi","family":"Kawarabayashi","sequence":"first","affiliation":[{"name":"National Institute of Informatics, Tokyo, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7408-6148","authenticated-orcid":false,"given":"Bojan","family":"Mohar","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Simon Fraser University, Burnaby, BC, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9826-704X","authenticated-orcid":false,"given":"Roman","family":"Nedela","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Faculty of Applied Sciences, University of West Bohemia in Pilsen, Plzen, Czech Republic and Mathematical Institute, Slovak Academy of Sciences, Bratislava, Slovakia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0071-9149","authenticated-orcid":false,"given":"Peter","family":"Zeman","sequence":"additional","affiliation":[{"name":"Technical University of Denmark, Lyngby, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,11,22]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(73)80002-0"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)00083-U"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190150605"},{"key":"e_1_3_2_5_2","first-page":"684","volume-title":"Proceedings of the 48th Annual ACM Symposium on Theory of Computing","author":"Babai L.","year":"2016","unstructured":"L. Babai. 2016. Graph isomorphism in quasipolynomial time. In Proceedings of the 48th Annual ACM Symposium on Theory of Computing. ACM, 684\u2013697."},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511600739"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1999.1939"},{"key":"e_1_3_2_8_2","volume-title":"Proceedings of the 4th Annual Mississippi Discrete Mathematics Workshop","author":"Brodnik A.","year":"2015","unstructured":"A. Brodnik, A. Malni\u010d, and R. Po\u017ear. 2015. Lower bounds on the simultaneous conjugacy problem in the symmetric group. In Proceedings of the 4th Annual Mississippi Discrete Mathematics Workshop."},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1090\/mcom\/3637"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22798"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1137\/0210015"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1201\/b21368"},{"key":"e_1_3_2_13_2","volume-title":"Generators and Relations for Discrete Groups","author":"Coxeter H. S. M.","year":"2013","unstructured":"H. S. M. Coxeter and W. O. J. Moser. 2013. Generators and Relations for Discrete Groups, Vol. 14. Springer Science & Business Media."},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1016\/0001-8708(77)90061-5"},{"key":"e_1_3_2_15_2","first-page":"49","article-title":"Calcul de centralisateur d\u2019un groupe de permutations","author":"Fontet M.","year":"1977","unstructured":"M. Fontet. 1977. Calcul de centralisateur d\u2019un groupe de permutations. Bulletin de la Societe Mathematique de France 49\u201350 (1977), 53\u201363.","journal-title":"Bulletin de la Societe Mathematique de France"},{"key":"e_1_3_2_16_2","volume-title":"Topological Graph Theory","author":"Gross J. L.","year":"2001","unstructured":"J. L. Gross and T. W. Tucker. 2001. Topological Graph Theory. Dover."},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1201\/b16132"},{"key":"e_1_3_2_18_2","volume-title":"Tilings and Patterns","author":"Gr\u00fcnbaum B.","year":"1987","unstructured":"B. Gr\u00fcnbaum and G. C. Shephard. 1987. Tilings and Patterns. Freeman."},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(82)90015-0"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(73)80013-3"},{"key":"e_1_3_2_21_2","volume-title":"Proceedings of the 6th Annual ACM Symppsium on Theory of Computing","author":"Hopcroft J. E.","year":"1974","unstructured":"J. E. Hopcroft and J. K. Wong. 1974. Linear time algorithm for isomorphism on planar graphs. In Proceedings of the 6th Annual ACM Symppsium on Theory of Computing."},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s3-37.2.273"},{"key":"e_1_3_2_23_2","unstructured":"K. Kawarabayashi. 2015. Graph isomorphism for bounded genus graphs in linear time. arXiv:1511.02460. Retreived from https:\/\/arxiv.org\/abs\/1511.02460"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/764\/15358"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374443"},{"key":"e_1_3_2_26_2","volume-title":"Proceedings of the 48th International Colloquium on Automata, Languages, and Programming (ICALP)","author":"Kawarabayashi K.","year":"2021","unstructured":"K. Kawarabayashi, B. Mohar, R. Nedela, and P. Zeman. 2021. Automorphisms and isomorphisms of maps in linear time. In Proceedings of the 48th International Colloquium on Automata, Languages, and Programming (ICALP)."},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/321892.321896"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.56021\/9780801866890"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1112\/S0024611597000245"},{"key":"e_1_3_2_30_2","first-page":"88:1","volume-title":"Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP)","volume":"168","author":"Neuen D.","year":"2020","unstructured":"D. Neuen. 2020. Hypergraph isomorphism for groups with restricted composition factors. In Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP). Leibniz International Proceedings in Informatics, Vol. 168, 88:1\u201388:19."},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01098279"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90010-4"},{"issue":"1","key":"e_1_3_2_33_2","first-page":"1","article-title":"Vertex-transitive maps on a torus","volume":"80","author":"\u0160uch Ondrej","year":"2011","unstructured":"Ondrej \u0160uch. 2011. Vertex-transitive maps on a torus. Acta Mathematica Universitatis Comenianae 80, 1 (2011), 1\u201330.","journal-title":"Acta Mathematica Universitatis Comenianae"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1991-1040045-3"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCT.1966.1082573"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.2307\/2371127"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3686798","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3686798","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:05:52Z","timestamp":1750291552000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3686798"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,22]]},"references-count":35,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,1,31]]}},"alternative-id":["10.1145\/3686798"],"URL":"https:\/\/doi.org\/10.1145\/3686798","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,11,22]]},"assertion":[{"value":"2022-05-04","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-07-05","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-11-22","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}