Linear time algorithm for isomorphism of planar graphs (Preliminary Report)

ABSTRACT

The isomorphism problem for graphs G1 and G2 is to determine if there exists a one-to-one mapping of the vertices of G1 onto the vertices of G2 such that two vertices of G1 are adjacent if and only if their images in G2 are adjacent. In addition to determining the existence of such an isomorphism, it is useful to be able to produce an isomorphism-inducing mapping in the case where one exists. The isomorphism problem for triconnected planar graphs is particularly simple since a triconnected planar graph has a unique embedding on a sphere [6]. Weinberg [5] exploited this fact in developing an algorithm for testing isomorphism of triconnected planar graphs in O(|V|2) time where V is the set consisting of the vertices of both graphs. The result has been extended to arbitrary planar graphs and improved to O(|V|log|V|) steps by Hopcroft and Tarjan [2,3]. In this paper, the time bound for planar graph isomorphism is improved to O(|V|). In addition to determining the isomorphism of two planar graphs, the algorithm can be easily extended to partition a set of planar graphs into equivalence classes of isomorphic graphs in time linear in the total number of vertices in all graphs in the set. A random access model of computation (see Cook [1]) is assumed. Although the proposed algorithm has a linear asymptotic growth rate, at the present stage of development it appears to be inefficient on account of a rather large constant. This paper is intended only to establish the existence of a linear algorithm which subsequent work might make truly efficient.

REFERENCES

• 1: Cook, S.A., "Linear time simulation of deterministic two-way pushdown automata," IFIP Congress 71: Foundations of Information Processing, Proceedings, Ljubljana, Yugoslavia, August, 1971;| 174-179, North-Holland Publishing Company, Amsterdam, 1972.
• 2: Hopcroft, J.E., and R.E. Tarjan, "A V log V algorithm for isomorphism of triconnected planar graphs," JCSS 7:3 (1973), 323-331.
• 3: Hopcroft, J.E., and R.E. Tarjan, "Isomorphism of planar graphs (working paper)," in Complexity of Computer Computations, (R.E. Miller and J.W. Thatcher (eds.), 143-150, Plenum Press, New York, 1972.
• 4: Ore, O. The Four Color Problem, Academic Press, New York, 1967, 48-61.
• 5: Weinberg, L., "A simple and efficient algorithm for determining isomorphism of planar triply connected graphs," IEEE Trans. on Circuit Theory 13(1966), 142-148.
• 6: Whitney, H., "A set of topological invariants for graphs," Amer. J. Math. 55(1933), 321-235.

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Reducibility and completeness

General Terms:
Theory