Document Open Access Logo

Automorphisms and Isomorphisms of Maps in Linear Time

Authors Ken-ichi Kawarabayashi, Bojan Mohar, Roman Nedela, Peter Zeman

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2021.86.pdf
  • Filesize: 0.66 MB
  • 15 pages

Document Identifiers

Author Details

Ken-ichi Kawarabayashi
  • National Institute of Informatics, Tokyo, Japan
Bojan Mohar
  • Department of Mathematics, Simon Fraser University, Burnaby, Canada
  • IMFM, Department of Mathematics, University of Ljubljana, Slovenia
Roman Nedela
  • Univeristy of West Bohemia, Pilsen, Czech Republic
Peter Zeman
  • Department of Applied Mathematics, Faculty of Mathematics and Physics, Charles University, Prague, Czech Republic

Funding

  • Kawarabayashi, Ken-ichi: JSPS Kakenhi Grant Number JP18H05291 and 20H05965
  • Mohar, Bojan: Supported in part by the NSERC Discovery Grant R611450 (Canada), and by the Research Project J1-2452 of ARRS (Slovenia).
  • Nedela, Roman: Supported by Slovak Research and Development Agency under Grant No. APVV-19-0308 and by GAČR 20-15576S.
  • Zeman, Peter: Supported by GAUK 1224120 and GAČR 20-15576S.

Cite As Get BibTex

Ken-ichi Kawarabayashi, Bojan Mohar, Roman Nedela, and Peter Zeman. Automorphisms and Isomorphisms of Maps in Linear Time. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 86:1-86:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ICALP.2021.86

Abstract

A map is a 2-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. When the underlying surface is orientable, every automorphism of a map determines an angle-preserving homeomorphism of the surface. While it is conjectured that there is no "truly subquadratic" 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, parametrized by the genus of the underlying surface. 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 uniform map in linear time. We also extend the algorithm to non-orientable surfaces by making use of the antipodal double-cover.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • maps on surfaces
  • automorphisms
  • isomorphisms
  • algorithm

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. L. Babai. Vertex-transitive graphs and vertex-transitive maps. Journal of graph theory, 15(6):587-627, 1991. Google Scholar
  2. L. Babai. Graph isomorphism in quasipolynomial time. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 684-697. ACM, 2016. Google Scholar
  3. L. Babai, D. Y. Grigoryev, and D. M. Mount. Isomorphism of graphs with bounded eigenvalue multiplicity. In Proceedings of the fourteenth annual ACM symposium on Theory of computing, pages 310-324. ACM, 1982. Google Scholar
  4. N. L. Biggs and A. T. White. Permutation groups and combinatorial structures, volume 33. Cambridge University Press, 1979. Google Scholar
  5. A. Brodnik, A. Malnič, and R. Požar. Lower bounds on the simultaneous conjugacy problem in the symmetric group. In 4th annual Mississippi Discrete Mathematics Workshop, 2015. Google Scholar
  6. A. Brodnik, A. Malnič, and R. Požar. Fast permutation-word multiplication and the simultaneous conjugacy problem. arXiv preprint, 2019. URL: http://arxiv.org/abs/1907.07889.
  7. C. J. Colbourn and K. S. Booth. Linear time automorphism algorithms for trees, interval graphs, and planar graphs. SIAM Journal on Computing, 10(1):203-225, 1981. Google Scholar
  8. M. Fontet. Calcul de centralisateur d’un groupe de permutations. Bull. Soc. Math. France Mém.,(49-50), pages 53-63, 1977. Google Scholar
  9. M. Grohe, D. Neuen, and P. Schweitzer. A faster isomorphism test for graphs of small degree. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 89-100, 2018. Google Scholar
  10. M. Grohe, D. Neuen, P. Schweitzer, and D. Wiebking. An improved isomorphism test for bounded-tree-width graphs. ACM Trans. Algorithms, 16(3):34:1-34:31, 2020. Google Scholar
  11. M. Grohe, D. Wiebking, and D. Neuen. Isomorphism testing for graphs excluding small minors. In 61st IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 625-636, 2020. Google Scholar
  12. J. L. Gross and T. W. Tucker. Topological graph theory. Dover, 2001. Google Scholar
  13. J. L. Gross, J. Yellen, and P. Zhang. Handbook of graph theory. Chapman and Hall/CRC, 2013. Google Scholar
  14. B. Grünbaum and G. C. Shephard. Tilings and patterns. Freeman, 1987. Google Scholar
  15. Christoph M Hoffmann. Subcomplete generalizations of graph isomorphism. Journal of Computer and System Sciences, 25(3):332-359, 1982. Google Scholar
  16. J. E. Hopcroft and R. Endre. Tarjan. A V log V algorithm for isomorphism of triconnected planar graphs. J. Comput. Syst. Sci., 7(3):323-331, 1973. Google Scholar
  17. J. E. Hopcroft and J. K. Wong. Linear time algorithm for isomorphism on planar graphs. In Proc. 6th Annual ACM Symp. on Theory of Computing., 1974. Google Scholar
  18. G. A. Jones and D. Singerman. Theory of maps on orientable surfaces. Proceedings of the London Mathematical Society, 3(2):273-307, 1978. Google Scholar
  19. K. Kawarabayashi. Graph isomorphism for bounded genus graphs in linear time. arXiv preprint, 2015. URL: http://arxiv.org/abs/1511.02460.
  20. K. Kawarabayashi, P. Klavík, B. Mohar, R. Nedela, and P. Zeman. Isomorphisms of maps on the sphere. In Polytopes and Discrete Geometry, volume 764 of Contemporary Mathematics, pages 125-147. American Mathematical Society, 2021. Google Scholar
  21. K. Kawarabayashi and B. Mohar. Graph and map isomorphism and all polyhedral embeddings in linear time. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 471-480. ACM, 2008. Google Scholar
  22. D. Lokshtanov, M. Pilipczuk, M. Pilipczuk, and S. Saurabh. Fixed-parameter tractable canonization and isomorphism test for graphs of bounded treewidth. SIAM Journal on Computing, 46(1):161-189, 2017. Google Scholar
  23. E. M. Luks. Isomorphism of graphs of bounded valence can be tested in polynomial time. Journal of computer and system sciences, 25(1):42-65, 1982. Google Scholar
  24. B. Mohar and C. Thomassen. Graphs on surfaces, volume 10. Johns Hopkins University Press, 2001. Google Scholar
  25. R. Nedela and M. Škoviera. Exponents of orientable maps. Proceedings of the London Mathematical Society, 75(1):1-31, 1997. Google Scholar
  26. D. Neuen. Hypergraph isomorphism for groups with restricted composition factors. In 47th International Colloquium on Automata, Languages, and Programming, (ICALP), volume 168 of LIPIcs, pages 88:1-88:19, 2020. Google Scholar
  27. I. N. Ponomarenko. The isomorphism problem for classes of graphs closed under contraction. Journal of Soviet Mathematics, 55(2):1621-1643, 1991. Google Scholar
  28. U. Schöning. Graph isomorphism is in the low hierarchy. Journal of Computer and System Sciences, 37(3):312-323, 1988. Google Scholar
  29. Ondrej Šuch. Vertex-transitive maps on a torus. Acta Math. Univ. Comenianae, 80(1):1-30, 2011. Google Scholar
  30. L. Weinberg. A simple and efficient algorithm for determining isomorphism of planar triply connected graphs. IEEE Transactions on Circuit Theory, 13(2):142-148, 1966. Google Scholar
  31. H. Whitney. 2-isomorphic graphs. American Journal of Mathematics, 55(1):245-254, 1933. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact