Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: A log-space algorithm for planar graph isomorphism
event speaker icon
Prajakta Nimbhorkar (The Institute of Mathematical Sciences)
event date icon
Wednesday, 19.08.2009, 15:00
event location icon
Room 337-8 Taub Bld.
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.