The graph isomorphism problem on geometric graphs

摘要: The graph isomorphism (GI) problem asks whether two given graphs are isomorphic or not. GI is quite basic and simple, however, it\textquoterights time complexity a long standing open problem. clearly in NP, no polynomial algorithm known, the not NP-complete unless hierarchy collapses. In this paper, we survey computational of on some classes that have geometric characterizations. Sometimes becomes solvable when add restrictions classes. properties these boundary indicate us essence difficulty We also show as hard general even for grid unit intersection torus, partially solves an