Homeomorphism of 2-complexes is equivalent to graph isomorphism
Whittlesey(12,13,14) gave a criterion which decides when two finite 3-dimensional complexes are homeomorphic. We show that graph isomorphism can be reduced efficiently to 2-complex homeomorphism, and that Whittlesey's criterion can be reduced efficiently to graph isomorphism. Therefore graph isomorphism and 2-complex homeomorphism are polynomial-time equivalent.
graph isomorphism computational topology np computational complexity