Graph isomorphism is an important and widely studied computational problem, with a yet unsettled complexity. However, the exact complexity is known for isomorphism of various classes of graphs. Recently [DLNTW09] proved that planar isomorphism is complete for log-space. We extend this result of [DLNTW09] further to the classes of graphs which exclude

Our algorithm for *K*_{3,3} minor-free graphs proceeds by decomposition into triconnected
components, which are known to be either planar or *K*_{5} components [Vazirani89]. This gives a triconnected component tree similar to that for planar graphs. An extension of the log-space algorithm of [DLNTW09] can then be used to decide the isomorphism problem.

For *K*_{5} minor-free graphs, it is known from [Khuller88] that the 4-connected components are either planar graphs or a four-rung mobius ladder on 8 vertices. We give an algorithm to get a unique
decomposition of *K*_{5} minor-free graphs into triconnected and four-connected planar components, and construct triconnected and four-connected component trees. As the algorithm of [DLNTW09] does not deal with four-connected component trees, it needs to be modified in a quite non-trivial way.