A polynomial-time algorithm for determining the isomorphism of graphs of fixed genus

ABSTRACT

The isomorphism problem for graphs has been in recent years the object of a much research (see e.g. [Col 78] or [Re-Cor 77]). Its complexity is still unknown. It is not known whether the problem is NP-complete, although it is NP, of course. It is not known whether there exists a polynomial-time algorithm for it. Recently, Babai [Ba 79] has discussed probabilistic algorithms. For additional information see also [Mi 77]. The problem has also some practical applications. Of the known algorithms let us only quote the work of Weinberg [We 66] and of Hopcroft and Tarjan [Ho-Ta 72]. Weinberg's algorithm rums in quadratic time (in &agr;o, the number of vertices of the graphs). Hopcroft and Tarjan's runs in time 0(&agr;o log&agr;o) and uses their powerful technique of depth-first search. Both these algorithms apply only to planar (Weinberg's only to 3-connected planar) graphs. They rely on a well-known rigidity theorem of Withney [Withney 32].

REFERENCES

• 1: L. Babai and L. Kucera, Canonical Labelling of Graphs in Linear Average Time, Proc. of the 20-th Annual Symp. Foundations of Computer Science, Oct 29-31, 1979, San Juan, Puerto Rico,(published by the IEEE Computer Society).
• 2: John Adrian Bondy, Graph Theory With Applications, Elsevier Science Ltd, 1976
• 3: C.J. Colbourn, A Bibliography of the Graph Isomorphism Problem, Technical Report no 123, Dept. of Computer Science, University of Toronto, 1978.
• 4: J. Edmonds, On the Surface Duality of Linear Graphs, J. Res. Natl. Bur. Standards-B. Mathematics and Mathematical Physics, 69.B, 1-2 (Jan.-June 1965), 121–123.
• 5: I.S. Filotti, An Algorithm for Imbedding Cubic Graphs in the Torus, J.C.S.S. 1980 (to appear).(A preliminary version of this paper was published in the Proc. Tenth Annual ACM Symp. Theory of Computing,) San Diego, California, May 1980.
• 6: 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]
• 7: A rigidity theorem for graph embeddings (unpublished).
• 8: J.E. Hopcroft and R.E. Tarjan, Isomorphism of Planar Graphs (Working Paper) in “Complexity of Computer Computations” (Miller et al. eds.), Plenum Press, 1972.
• 9: J.B. Kruskal, On the Shortest Spanning Subtree of a Graph and the Travelling Salesman Problem, Proc. Amer. Math. Soc., 7 (1956), 48–50.
• 10: Gary L. Miller, Graph isomorphism, general remarks, Proceedings of the ninth annual ACM symposium on Theory of computing, p.143-150, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803404]
• 11: R.C. Read and D.G. Corneil, The Graph Isomorphism Disease, J. Graph Theory, 1, 339–363 (1977).
• 12: Edward M. Reingold , Jurg Nievergelt , Narsingh Deo, Combinatorial Algorithms: Theory and Practice, Prentice Hall College Div, 1977
• 13: W.T. Tutte, “Connectivity in Graphs”, U. of Toronto Press, Toronto 1966.
• 14: L. Weinberg, A Simple and Efficient Algorithm for Determining Isomorphism of Planar Triply Connected Graphs, IEEE Trans. on Circuit Theory, CT-13, 2 (1966), 142–148.
• 15: A. White, “Graphs, Groups and Surfaces”, North-Holland Publishing Co., American Elsevier Co., New York, 1973.
• 16: H. Whitney, “Congruent Graphs and the Connectivity of Graphs”, Amer. J. Math., 54 (1932), 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

General Terms:
Theory