Homeomorphism of 2-complexes is equivalent to graph isomorphism

Authors
Dunlaing, CO Watt, C Wilkins, D
Citation
Co. Dunlaing et al., Homeomorphism of 2-complexes is equivalent to graph isomorphism, INT J C GEO, 10(5), 2000, pp. 453-476
Citations number
16
Categorie Soggetti
Engineering Mathematics
Journal title
INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS
ISSN journal
02181959 → ACNP
Volume
10
Issue
5
Year of publication
2000
Pages
453 - 476
Database
ISI
SICI code
0218-1959(200010)10:5<453:HO2IET>2.0.ZU;2-F
Abstract
Whittlesey(12,13,14) gave a criterion which decides when two finite 3-dimen sional complexes are homeomorphic. We show that graph isomorphism can be re duced efficiently to 2-complex homeomorphism, and that Whittlesey's criteri on can be reduced efficiently to graph isomorphism. Therefore graph isomorp hism and 2-complex homeomorphism are polynomial-time equivalent.