10
$\begingroup$

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.

$\endgroup$
15
$\begingroup$

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.

$\endgroup$
  • 5
    $\begingroup$ You're making perfect sense. I was going to give pretty much the same answer. $\endgroup$ – Peter Shor Jan 8 '11 at 16:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.