Automorphisms and Isomorphisms of Maps in Linear Time
Article No.: 6, Pages 1 - 32
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. 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 on an orientable surface of genus \(g\neq 0\), parametrized by the genus \(g\). A map on an orientable surface is uniform if the cyclic vector of sizes of faces incident to a vertex \(v\) does not depend on the choice of \(v\). 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.
References
[1]
A. Altshuler. 1973. Construction and enumeration of regular maps on the torus. Discrete Mathematics 4 (1973), 201–217.
[2]
Alberto Apostolico, Dany Breslauer, and Zvi Galil. 1993. Parallel detection of all palindromes in a string. Theoretical Computer Science 141 (1993), 163–173.
[3]
L. Babai. 1991. Vertex-transitive graphs and vertex-transitive maps. Journal of Graph Theory 15, 6 (1991), 587–627.
[4]
L. Babai. 2016. Graph isomorphism in quasipolynomial time. In Proceedings of the 48th Annual ACM Symposium on Theory of Computing. ACM, 684–697.
[5]
N. L. Biggs and A. T. White. 1979. Permutation Groups and Combinatorial Structures, Vol. 33. Cambridge University Press.
[6]
C.Paul Bonnington, M.J. Grannell, T.S. Griggs, and J. Širáň. 2000. Exponential families of non-isomorphic triangulations of complete graphs. Journal of Combinatorial Theory, Series B 78, 2 (2000), 169–184.
[7]
A. Brodnik, A. Malnič, and R. Požar. 2015. Lower bounds on the simultaneous conjugacy problem in the symmetric group. In Proceedings of the 4th Annual Mississippi Discrete Mathematics Workshop.
[8]
Andrej Brodnik, Aleksander Malnič, and Rok Požar. 2021. The simultaneous conjugacy problem in the symmetric group. Mathematics of Computation 90, 332 (2021), 2977–2995, 2021.
[9]
Andrej Brodnik, Aleksander Malnič, and Rok Požar. 2022. A subquadratic algorithm for the simultaneous conjugacy problem. Journal of Graph Theory 100, 4 (2022), 630–637.
[10]
C. J. Colbourn and K. S. Booth. 1981. Linear time automorphism algorithms for trees, interval graphs, and planar graphs. SIAM Journal on Computing 10, 1 (1981), 203–225, 1981.
[11]
J. H. Conway, H. Burgiel, and C. Goodman-Strauss. 2016. The Symmetries of Things. CRC Press.
[12]
H. S. M. Coxeter and W. O. J. Moser. 2013. Generators and Relations for Discrete Groups, Vol. 14. Springer Science & Business Media.
[13]
S. Fisk. 1977. Geometric coloring theory. Advances in Mathematics 24, 3 (1977), 298–340.
[14]
M. Fontet. 1977. Calcul de centralisateur d’un groupe de permutations. Bulletin de la Societe Mathematique de France 49–50 (1977), 53–63.
[15]
J. L. Gross and T. W. Tucker. 2001. Topological Graph Theory. Dover.
[16]
J. L. Gross, J. Yellen, and P. Zhang. 2013. Handbook of Graph Theory. Chapman and Hall/CRC.
[17]
B. Grünbaum and G. C. Shephard. 1987. Tilings and Patterns. Freeman.
[18]
Christoph M Hoffmann. 1982. Subcomplete generalizations of graph isomorphism. Journal of Computer and System Sciences 25, 3 (1982), 332–359.
[19]
J. E. Hopcroft and R. Endre. Tarjan. 1973. A V log V algorithm for isomorphism of triconnected planar graphs. The Journal of Computer and System Sciences 7, 3 (1973), 323–331.
[20]
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.
[21]
G. A. Jones and D. Singerman. 1978. Theory of maps on orientable surfaces. Proceedings of the London Mathematical Society 3, 2 (1978), 273–307.
[22]
K. Kawarabayashi. 2015. Graph isomorphism for bounded genus graphs in linear time. arXiv:1511.02460. Retreived from https://arxiv.org/abs/1511.02460
[23]
K. Kawarabayashi, P. Klavík, B. Mohar, R. Nedela, and P. Zeman. 2021. Isomorphisms of maps on the sphere. In Polytopes and Discrete Geometry, Vol. 764: Contemporary Mathematics. American Mathematical Society, 125–147.
[24]
K. Kawarabayashi and B. Mohar. 2008. Graph and map isomorphism and all polyhedral embeddings in linear time. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing. ACM, 471–480.
[25]
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).
[26]
Glenn Manacher. 1975. A new linear-time “on-line” algorithm for finding the smallest initial palindrome of a string. Journal of the ACM 22, 3 (1975), 346–351.
[27]
B. Mohar and C. Thomassen. 2001. Graphs on Surfaces, Vol. 10. Johns Hopkins University Press.
[28]
R. Nedela and M. Škoviera. 1997. Exponents of orientable maps. Proceedings of the London Mathematical Society 75, 1 (1997), 1–31.
[29]
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–88:19.
[30]
I. N. Ponomarenko. 1991. The isomorphism problem for classes of graphs closed under contraction. Journal of Soviet Mathematics 55, 2 (1991), 1621–1643.
[31]
U. Schöning. 1988. Graph isomorphism is in the low hierarchy. Journal of Computer and System Sciences 37, 3 (1988), 312–323.
[32]
Ondrej Šuch. 2011. Vertex-transitive maps on a torus. Acta Mathematica Universitatis Comenianae 80, 1 (2011), 1–30.
[33]
C. Thomassen. 1991. Tilings of the torus and the Klein bottle and vertex-transitive graphs on a fixed surface. Transactions of the American Mathematical Society 323, 2 (1991), 605–635.
[34]
L. Weinberg. 1966. A simple and efficient algorithm for determining isomorphism of planar triply connected graphs. IEEE Transactions on Circuit Theory 13, 2 (1966), 142–148.
[35]
H. Whitney. 1933. 2-isomorphic graphs. American Journal of Mathematics 55, 1 (1933), 245–254.
Index Terms
- Automorphisms and Isomorphisms of Maps in Linear Time
Recommendations
Monomial isomorphisms of cyclic codes
For codes, there are multiple notions of isomorphism. For example, we can consider isomorphisms that only permute the coordinates of codewords, or isomorphisms that not only permute the coordinates of codewords but also multiply each coordinate by a ...
On Isomorphisms of Marušič---Scapellato Graphs
Marušiă ---Scapellato graphs are vertex-transitive graphs of order $$m(2^k + 1)$$m(2k+1), where m divides $$2^k - 1$$2k-1, whose automorphism group contains an imprimitive subgroup that is a quasiprimitive representation of $$\mathrm{SL}(2,2^k)$$SL(2,2k)...
Cayley bipolar fuzzy graphs associated with bipolar fuzzy groups
Recently, bipolar fuzzy graph is a growing research topic as it is the generalisation of fuzzy graphs. Let G be a non-trivial group and S be a non-empty subset of G such that not containing the identity element of G and S = S-1 = {s-1| s ∈ S}. The Cayley ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 22 November 2024
Online AM: 07 August 2024
Accepted: 05 July 2024
Revised: 23 May 2024
Received: 04 May 2022
Published in TALG Volume 21, Issue 1
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- JSPS Kakenhi
- JSPS Kakenhi
- JST ASPIRE
- NSERC Discovery
- Slovak Research and Development Agency
- GAČR
- Carlsberg Foundation Young Researcher Fellowship
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 93Total Downloads
- Downloads (Last 12 months)93
- Downloads (Last 6 weeks)35
Reflects downloads up to 07 Jan 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in