2
\$\begingroup\$

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.

\$\endgroup\$
  • 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.