1980/01/01 by Gary L. Miller · 148 citations
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Advanced Graph Theory Research #Algorithms and Data Compression #Graph isomorphism #Combinatorics #Isomorphism (crystallography) #Mathematics #Embedding #Graph homomorphism #Discrete mathematics #Genus #Induced subgraph isomorphism problem #Graph #Computer science #Line graph #Voltage graph #Artificial intelligence #Crystal structure #Crystallography
paper · pdf · doi:10.1145/800141.804670
openalex publication_date 1980/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
We present an algorithm which determines isomorphism of graphs in vO(g)steps where v is the number of vertices and g is the genus of the graphs. In [FMR 79] an algorithm was presented for embedding graph on surfaces of genus g in vO(g) steps. Here we show how to extend this algorithm to isomorphism testing for graphs of small genus. This result is noteworthy for at least two reasons. First, this extends the polynomial time isomorphism results for the plane [HT 72] and also the projective plane [L 80] to arbitrary surfaces. Second, this gives one of the few known natural decompositions of the isomorphism problem into an infinite hierarchy of problems Po,P1,... such that isomorphism testing of problems in P1 is decidable in time vO(i).