Graph Isomorphism for K_{3,3}-free and K_5-free graphs is in Log-space

Samir Datta, Prajakta Nimbhorkar, Thomas Thierauf & Fabian Wagner
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, \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$ as a minor, and give a log-space algorithm. Our algorithm decomposes $K_{3,3}$ minor-free graphs into biconnected and those further into...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.