Let's assume a set of finite number of random points embedded in a 2-periodic 2D cell. Constructing Delaunay triangulation from these points gives a graph in a torus geometry where each intial point is a vertex and each triangulation edge is a graph edge, hence creating a toroidal graph. I also assume the set of points to be not degenerate, giving unique triangulation.
visual example of a periodic Delaunay graph
I'm interested in finding isomorphic graphs created from equinumerous sets of points.
What I already know:
- graph isomorphism is generally an unsolved problem and belongs to NP
- there are numerous graph invariants that are necessary but not sufficient for general case, including vertices and edges count, vertices degrees and degrees sequences
- some particular types of graphs have known solutions of polynomial or even linear complexity.
My question is: are there any isomorphic invariants specific to the graphs described above or some heuristics for testing isomorphism that are consequence of any (maybe some less obvious) characteristics of such graphs? (each face being bound by exactly 3 edges, Delaunay triangulation having unique dual graph etc.)
My intuition is constantly going back to the idea of finding a path in both graphs (probably a cycle) that would go through identical sequence of vertices degree (not necessarily ordered sequence, for example path going consecutively through 5-degree vertex, then 3, then 6 etc). Unfortunately I have not studied math so either proving or disproving this method is way beyond my skills.