Graph isomorphism is an important and widely studied computational problem witha yet unsettled complexity.However, the exact complexity is known for isomorphism of various classes ofgraphs. Recently, cite{DLNTW09} proved that planar isomorphism is complete for log-space.We extend this result %of cite{DLNTW09} further to the classes of graphs which exclude $K_{3,3}$ or $K_5$ asa minor, and give a log-space algorithm.Our algorithm decomposes $K_{3,3}$ minor-free graphs into biconnected and those further into triconnectedcomponents, which are known to be either planar or $K_5$ components cite{Vaz89}. This gives a triconnectedcomponent tree similar to that for planar graphs. An extension of the log-space algorithm of cite{DLNTW09}can then be used to decide the isomorphism problem.For $K_5$ minor-free graphs, we consider $3$-connected components.These are either planar or isomorphic to the four-rung mobius ladder on $8$ verticesor, with a further decomposition, one obtains planar $4$-connected components cite{Khu88}.We give an algorithm to get a uniquedecomposition of $K_5$ minor-free graphs into bi-, tri- and $4$-connected components,and construct trees, accordingly.Since the algorithm of cite{DLNTW09} doesnot deal with four-connected component trees, it needs to be modified in a quite non-trivial way.
展开▼
