Generating all possible 3-connected graphs

Question

There is a conjecture by Tutte and Thomassen (Planarity and duality of finite and infinite graphs, 1979) saying this

A 3-connected graph can be obtained from a wheel by succestively adding an edge and splitting a vertex into two adjacent vertices of degree at least three such that the edge joining them is not contained in a 3-cycle. If we apply a more general splitting operation (i.e., we allow the edge joining the two new vertices to be contained in a 3-cycle) then we can start out with K_4, and we need only the splitting operation in order to generate all 3-connected graphs.

I am trying to implement the last stated operation using iGraph with Python.

I want to define a function splitVertex(g,v), taking a graph g and a vertex v, and then have it split v in all the possible ways as the operation defines. Then I want a list of all these new graphs, and I will do some further work on them.

At this point, I have the following function creating two new vertices x and y, which would be the newly created vertices after the split.

def splitVertex(g,v):
    numver = g.vcount()

    g.add_vertices(2)

   x = numver
    y = numver+1

    g.add_edges([(x,y)])

Can somebody please help me out with a nice way to implement this? I know this will generate a massive amount of data, but that is alright, I have plenty of time ;)

Edit: Of course this have to be controlled in some way since the number of 3-connected graphs is infinite, but that is not what this question concerns.

Answer 1

Based on Keith's solution. This is totally untested, but I guess the general idea is OK. This version generates the splits instead of returning all of them at once.

from itertools import chain, combinations

def powerset(iterable):
    "Returns all the possible subsets of the elements in a given iterable"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

def partition(iterable):
    "Returns all the possible ways to partition a set into two subsets"
    s = set(iterable)
    for s1 in powerset(s):
        yield s1, s-s1

def split_vertex(graph, v1):
    # Note that you only need one extra vertex, you can use v for the other
    v2 = graph.vcount()
    graph.add_vertices(1)

    # Find the neighbors of v1
    neis = set(graph.neighbors(v1))

    # Delete all the edges incident on v1 - some of them will be re-added
    g.delete_edges(g.incident(v1))

    # Iterate over the powerset of neis to find all possible splits
    for set1, set2 in partition(neis):
        if len(set1) < 2 or len(set2) < 2:
            continue

        # Copy the original graph
        g2 = g.copy()

        # Add edges between v1 and members of set1
        g2.add_edges([(v1, v3) for v3 in set1])

        # Add edges between v2 and members of set2
        g2.add_edges([(v2, v3) for v3 in set2])

        # Return the result
        yield g2

Answer 2

Your splitting operation should be a bit more involved. You need to modify all the edges that used to connect to v to connect to x or y instead.

def splitVertex(g,v):
  numver = g.vcount()
  g.add_vertices(2)
  x = numver
  y = numver+1
  g.add_edges([(x,y)])

  neighbors = g.neighbors(v)
  g.delete_vertices([v])

  new_graphs = []
  for (neighbors_of_x, neighbors_of_y) in set_split(neighbors):
    if len(neighbors_of_x) < 2: continue
    if len(neighbors_of_y) < 2: continue
    g2 = g.copy()
    g2.add_edges(map(lambda neighbor_of_x: [neighbor_of_x, x], neighbors_of_x))
    g2.add_edges(map(lambda neighbor_of_y: [neighbor_of_y, y], neighbors_of_y))
    new_graphs.add(g2)
  return new_graphs

Where set_split should generate all possible ways of splitting neighbors into two sets.

You then need to generate all possible choices for v and apply them to each graph.

You will likely get lots of isomorphic graphs. I imagine there is a better way to do all of this, can't think of it off the top of my head.