The Taub Faculty of Computer Science Events and Talks

Graph isomorphism is an important problem and has received lot of attention over several years. Its complexity is still open. There have been polynomial-time algorithms for several subclasses of graphs, including planar graphs. For isomorphism of some of these graph classes, the focus has been on determining the parallel complexity. The goal has been to show the isomorphism problem for various graph classes to be complete for some natural complexity class.

For planar graph isomorphism, the log-space lower bound was known, and there has been a wide gap between the upper and lower bounds. Our result closes this gap by giving an upper bound which matches the lower bound. Thus it settles the complexity of planar graph isomorphism by giving a log-space algorithm.

Joint work with: Samir Datta, Nutan Limaye, Thomas Thierauf and Fabian Wagner.