[birktj]

Note that the subgraph isomorphism problem [1] is NP-complete (also for planar graphs). There are very efficient data structures like k-d trees [2] that can be used to efficiently search for points in euclidean spaces, doing something similar for graphs would be quite difficult.

[1]: https://en.wikipedia.org/wiki/Subgraph_isomorphism_problem

[2]: https://en.wikipedia.org/wiki/K-d_tree

[EDIT]:

Graph canonization [3] on the other hand is not known to be either polynomial time solvable (I think it is for planar graphs though) or NP-complete and has implementations that are quite efficient in practice. It can be used to search for the exact same graph, but again extending to searching for similar graphs is probably quite difficult.

[3]: https://en.wikipedia.org/wiki/Graph_canonization