Essentially, this is a variation of Comparing Two Tree Structures, however I do not have "trees", but rather another type of graph.

I need to know what kind of Graph I have in order to figure out if there's a Graph Isomorphism Special Case...

Pictures of Graphs

As you can see, they are:

  • Not Directed
  • Not A Tree
  • Cyclic
  • Max 4 connections

But I still don't know the correct terminology, nor the which Isomorphism algorithm to pursue, guidance appreciated.


closed as off-topic by Josh Dec 20 '13 at 18:01

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Programming questions that aren't specific to game development are off-topic here, but can be asked on Stack Overflow. A good rule of thumb is to ask yourself "would a professional game developer give me a better/different/more specific answer to this question than other programmers?"" – Josh
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 4
    \$\begingroup\$ these are all Planar graphs \$\endgroup\$ – Jimmy Oct 17 '13 at 22:15
  • 4
    \$\begingroup\$ I've seen these occasionally called 'lattice subgraphs' or 'grid subgraphs' but that terminology doesn't seem to be as common as I was expecting. In addition to being planar as Jimmy notes, they're also 'bounded-degree', and furthermore they're bipartite (nodes can be colored Red and Green with each Red node connected only to Green nodes and vice versa). \$\endgroup\$ – Steven Stadnicki Oct 17 '13 at 22:55
  • 1
    \$\begingroup\$ One additional question: do you need 'true' isomorphism here, or do you want the lattice respected as well? (e.g., should a 'straight line' of five links be considered isomorphic to a 'staircase' of alternating up/down and left/right links?) \$\endgroup\$ – Steven Stadnicki Oct 17 '13 at 22:56
  • \$\begingroup\$ @Jimmy - Planar! That's the ticket! \$\endgroup\$ – oodavid Oct 18 '13 at 9:32
  • \$\begingroup\$ @StevenStadnicki - Respecting the lattice would be too easy ;-) \$\endgroup\$ – oodavid Oct 18 '13 at 9:33

Browse other questions tagged or ask your own question.