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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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