Homeomorphism of 2-Complexes is Graph Isomorphism Complete

DOI10.1137/S0097539791198900MaRDI QIDQ4286232zbMATH OpenOpenAlexFDO

Authors John Shawe-Taylor, Tomaž Pisanski

Publication date 27 March 1994

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539791198900

zbMATH Keywords

graph isomorphism2- complex homeomorphismcomplexity class of ISOMORPHISM-complete problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Triangulating manifolds (57Q15)

Recommendations

• HOMEOMORPHISM OF 2-COMPLEXES IS EQUIVALENT TO GRAPH ISOMORPHISM
• scientific article; zbMATH DE number 1186915
• Isomorphisms and homeomorphisms of a class of graphs and spaces
• Complexes of graph homomorphisms
• Homologies of complexes of doubly connected graphs
• scientific article; zbMATH DE number 5990556
• The universality of Hom complexes of graphs
• Compactifications of the homeomorphism group of a graph
• Graph homomorphisms with complex values: a dichotomy theorem
• Homomorphisms of 2-edge-colored graphs

Cited in

(7)

• scientific article; zbMATH DE number 4011932 (Why is no real title available?)
• Drawing graphs by eigenvectors: theory and practice
• Aspects of topology, genus and isomerism in closed 3-valent networks
• Parametrized complexity of expansion height
• HOMEOMORPHISM OF 2-COMPLEXES IS EQUIVALENT TO GRAPH ISOMORPHISM
• Testing homotopy equivalence is isomorphism complete
• On the isomorphism of expressions

This page was built for publication: Homeomorphism of 2-Complexes is Graph Isomorphism Complete

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4286232)