Is there a polynomial-time algorithm to solve graph isomorphism for Delaunay graphs of (finite) hexagonal tessellations?
I guess all those subgraphs will be planer graphs. And I think that there is efficient algorithm for isomorphism of planer graphs.
ref: Linear time algorithm for isomorphism of planar graphs by     J. E. Hopcroft
J. K. Wong
NOTE: I am not an expert and might not be making any sense.