Isomorphism testing for graphs of bounded genus

ABSTRACT

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).

REFERENCES

• 1: J. Edmonds, Private Communication.
• 2: I.S. Filotti, G. L. Miller and J. Reif “On Determining the Genus of a Graph in 0(V 0(g)) Steps,” STOC 1979.
• 3: P. Gacs and L. Lovasz “Khachian's Algorithm for Linear Programming” Stanford Technical Report #STAN-CS-79-750.
• 4: J. E. Hopcroft and R. E. Tarjan “Isomorphism of Planar Graphs (working paper) Complexity of Computer Computations” (R. E. Miller,; J. W. Thatcher, eds) Plenum, 1972, 131–152.
• 5: J. E. Hopcroft and R. E. Tarjan “Dividing A Graph into Triconnected Components” SIAM J. Comput., Vol. 2, No. 3, Sept. 1973, 294–303.
• 6: John Hopcroft , Robert Tarjan, Efficient Planarity Testing, Journal of the ACM (JACM), v.21 n.4, p.549-568, Oct. 1974 [doi>10.1145/321850.321852]
• 7: J. E. Hopcroft , J. K. Wong, Linear time algorithm for isomorphism of planar graphs (Preliminary Report), Proceedings of the sixth annual ACM symposium on Theory of computing, p.172-184, April 30-May 02, 1974, Seattle, Washington, United States [doi>10.1145/800119.803896]
• 8: R. M. Karp, “Reducibility Among Combinatorial Problems”, Complexity of Computer Computations (R. E. Miller and J. W. Thatcher, ed) Plenum Press, 1972.
• 9: N. N. Kazarinoff “Analytic Inequality”, Holt, Rinehart and Winston, (1964).
• 10: L. G. Khachian “Polynomial Algorithm for Linear Programming” Doklady Adademii Nauk SSSR, 1979, Vol. 244, No. 5, 1093–1096.
• 11: David Lichtenstein, Isomorphism for graphs embeddable on the projective plane, Proceedings of the twelfth annual ACM symposium on Theory of computing, p.218-224, April 28-30, 1980, Los Angeles, California, United States [doi>10.1145/800141.804669]
• 12: G. L. Miller “Riemann's Hypothesis and Tests for Primality”, JCSS Vol. 13, No. 3, Dec. 1976, pp. 300–317.
• 13: G. L. Miller, “Graph Isomorphism, General Remark” JCSS, Vol. 18, No. 2, April, 1979, pp. 128–141.
• 14: G. L. Miller, “Poincare Intersection Numbers and Some Application” (to appear).
• 15: I. S. Filotti , Jack N. Mayer, A polynomial-time algorithm for determining the isomorphism of graphs of fixed genus, Proceedings of the twelfth annual ACM symposium on Theory of computing, p.236-243, April 28-30, 1980, Los Angeles, California, United States [doi>10.1145/800141.804671]
• 16: L. G. Valiant, “The Complexity of Enumeration and Reliability Problems” SIAM J Comput. Vol. 8 No. 3, August 1979, pp. 410–421.
• 17: H. Whitney, “A Set of Topological Invariants for Graphs,” American J. Math 55 (1933) pp. 321–235.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Proof theory

General Terms:
Theory