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

摘要

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.