Compatible topologies on graphs: An application to graph isomorphism problem complexity

On one hand the graph isomorphism problem (GI) has received considerable attention due to its unresolved complexity status and its many practical applications. On the other hand a notion of compatible topologies on graphs has emerged from digital topology (see [A. Bretto, Comparability graphs and digital topology, Comput. Vision Graphic Image Process. (Image Understanding), 82 (2001) 33–41; J.M. Chassery, Connectivity and consecutivity in digital pictures, Comput. Vision Graphic Image Process. 9 (1979) 294–300; L.J. Latecki, Topological Connectedness and 8-connectness in digital pictures, CVGIP Image Understanding 57(2) (1993) 261–262; U. Eckhardt, L.J. Latecki, Topologies for digital spaces Z2 and Z3, Comput. Vision Image Understanding 95 (2003) 261–262; T.Y. Kong, R. Kopperman, P.R. Meyer, A topological approach to digital topology, Amer. Math. Monthly Archive 98(12) (1991) 901–917; R. Kopperman, Topological digital topology, Discrete geometry for computer imagery, 11th International Conference, Lecture Notes in Computer Science, Vol. 2886, DGCI 2003, Naples, Italy, November 19–21, pp. 1–15]).In this article we study GI from the topological point of view. Firstly, we explore the poset of compatible topologies on graphs and in particular on bipartite graphs. Then, from a graph we construct a particular compatible Alexandroff topological space said homeomorphic-equivalent to the graph. Conversely, from any Alexandroff topology we construct an isomorphic-equivalent graph on which the topology is compatible. Finally, using these constructions, we show that GI is polynomial-time equivalent to the topological homeomorphism problem (TopHomeo). Hence GI and TopHomeo are in the same class of complexity.