TR10-050 Authors: Samir Datta, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner

Publication: 25th March 2010 13:09

Downloads: 2267

Keywords:

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 [DLN$^+$09] proved that planar graph isomorphism is complete for log-space.

We extend this result of [DLN$^+$09] further

to the classes of graphs which exclude $K_{3,3}$ or $K_5$ as

a minor, and give a log-space algorithm.

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 [Vaz89]. This gives a triconnected

component tree similar to that for planar graphs. An extension of the log-space algorithm of [DLN$^+$09]

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$ vertices

or, with a further decomposition, one obtains planar $4$-connected components [Khu88].

We give an algorithm to get a unique

decomposition of $K_5$ minor-free graphs into bi-, tri- and $4$-connected components,

and construct trees, accordingly.

Since the algorithm of [DLN$^+$09] does

not deal with four-connected component trees, it needs to be modified in a quite non-trivial way.