Isomorphism for K3,3-free Graphs and K5-free Graphs in Log-Space

Samir Datta, Prajakta Nimbhorkar, Thomas Thierauf and Fabian Wagner

Abstract:
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 K3,3 or K5 as a minor, and give a log-space algorithm.

Our algorithm for K3,3 minor-free graphs proceeds by decomposition into triconnected components, which are known to be either planar or K5 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 K5 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 K5 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.