Automorphisms and isomorphisms of maps in linear time

DOI10.1145/3686798MaRDI QIDQ7023523zbMATH OpenFDO

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

Publication date 21 February 2025

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3686798

zbMATH Keywords

automorphismisomorphismlinear-time algorithmmaps on surfaces

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Relations of low-dimensional topology with graph theory (57M15) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Analysis of algorithms (68W40)

Cites work

• 2-isomorphic graphs.
• A New Linear-Time ``On-Line Algorithm for Finding the Smallest Initial Palindrome of a String
• A subquadratic algorithm for the simultaneous conjugacy problem
• A V log V algorithm for isomorphism of triconnected planar graphs
• Construction and enumeration of regular maps on the torus
• Exponential families of non-isomorphic triangulations of complete graphs
• Exponents of Orientable Maps
• Geometric coloring theory
• Graph isomorphism in quasipolynomial time (extended abstract)
• Graph isomorphism is in the low hierarchy
• Graphs on surfaces
• scientific article; zbMATH DE number 3645098 (Why is no real title available?)
• scientific article; zbMATH DE number 5485559 (Why is no real title available?)
• scientific article; zbMATH DE number 3968590 (Why is no real title available?)
• scientific article; zbMATH DE number 3575612 (Why is no real title available?)
• scientific article; zbMATH DE number 3585658 (Why is no real title available?)
• Isomorphisms of maps on the sphere
• Linear Time Automorphism Algorithms for Trees, Interval Graphs, and Planar Graphs
• Parallel detection of all palindromes in a string
• Subcomplete generalizations of graph isomorphism
• The isomorphism problem for classes of graphs closed under contraction
• The simultaneous conjugacy problem in the symmetric group
• Theory of Maps on Orientable Surfaces
• Tilings of the Torus and the Klein Bottle and Vertex-Transitive Graphs on a Fixed Surface
• Topological graph theory.
• Vertex-transitive graphs and vertex-transitive maps
• Vertex-transitive maps on a torus

This page was built for publication: Automorphisms and isomorphisms of maps in linear time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7023523)