Given a finite plane, I have a hexagonal tessellation of that plane with a fixed-size regular hexagon. I then compute the Delaunay graph G for the tessellation. Given such a graph G, I delete specific sets of nodes in that graph to yield multiple subgraphs of G. I need to determine if these subgraphs are isomorphic (to each other).
Does there exist a polynomial-time algorithm to do so?
I know that there is no know poly-time algorithm for solving graph isomorphism in the general case. But I am not sure if it is still the case for such specific Delaunay graphs.