Isomorphism for graphs embeddable on the projective plane

ABSTRACT

There are no known polynomial time algorithms for graph isomorphism. For certain classes of graphs, however, efficient algorithms have been found. In particular, there is a polynomial time algorithm for isomorphism of planar graphs [4,5]. This paper presents a generalization of the third theorem to the projective plane, allowing a straightforward adaptation of the planar algorithm to the projective plane. Gary Miller has subsequently generalized my result to surfaces of arbitrary genus, so that there is now a graph isomorphism algorithm which is polynomial for any fixed genus.

REFERENCES

• 1: I. S. Filotti , Gary L. Miller , John Reif, On determining the genus of a graph in O(v O(g)) steps(Preliminary Report), Proceedings of the eleventh annual ACM symposium on Theory of computing, p.27-37, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804395]
• 2: Hopcroft, J.E., R.E. Tarjan, Dividing a Graph into Triconnected Components, SIAM J. on Computing, 2:3, September, 1973, pp. 135–158.
• 3: 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]
• 4: Hopcroft, J.E., R.E. Tarjan, Isomorphism of Planar Graphs, in Complexity of Computations, R. Miller, J. Thatcher, eds., Plenum Press, New York, 1972, pp. 143–150.
• 5: 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]
• 6: Lempel, A., S. Even, I. Cederbaum, An Algorithm for Planarity Testing of Graphs, in Theory of Graphs, International Symposium: Rome, July, 1966, pp. 215–232, Gordon and Breach, New York, 1967.
• 7: Mac Lane, S., A Structural Characterization of Planar Combinatorial Graphs, Duke Math. J., 3 (1937), pp. 460–472.
• 8: Weinberg, L., A Simple and Efficient Algorithm for Determining Isomorphism of Planar Triply Connected Graphs, IEEE Trans. Circuit Theory CT-13 (1966), pp. 142–148.
• 9: Whitney, H., Congruent Graphs and the Connectivity of Graphs, American J. of Math. 54 (1932), pp. 150–168.

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on polynomials

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Theory