<p>I guess all those subgraphs will be planer graphs. And I think that there is efficient algorithm for isomorphism of planer graphs.</p>
<p>ref: <a href="http://portal.acm.org/citation.cfm?doid=800119.803896" rel="noreferrer">Linear time algorithm for isomorphism of planar graphs by     J. E. Hopcroft<br />
J. K. Wong</a></p>
<p><em>NOTE: I am not an expert and might not be making any sense.</em></p>

CC BY-SA 2.5
2011-01-08T16:45:58.840Z
You're making perfect sense. I was going to give pretty much the same answer.
Peter Shor 
CC BY-SA 2.5
2011-01-08T16:00:53.260Z
2011-01-08T16:00:53.260Z
2020-06-17T09:38:08.363Z
Pratik Deoghare
<p>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).</p>

<p>Does there exist a polynomial-time algorithm to do so?</p>

<p>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. </p>

<ds.algorithms><graph-algorithms><graph-isomorphism>
Is there a polynomial-time algorithm to solve graph isomorphism for Delaunay graphs of (finite) hexagonal tessellations?
Srikanth Sastry
# Is there a polynomial-time algorithm to solve graph isomorphism for Delaunay graphs of (finite) hexagonal tessellations?

(Asked by: username_0 on 2011-01-08)

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.

**Tags:** ds.algorithms, graph-algorithms, graph-isomorphism


---

## 1 answers

### Answer by username_1 on 2011-01-08. Score: 15 | Accepted answer

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](http://portal.acm.org/citation.cfm?doid=800119.803896)

*NOTE: I am not an expert and might not be making any sense.*

> **Comments:**
> **username_2**: You're making perfect sense. I was going to give pretty much the same answer.  

---

