1316.sagews

def is_outer_planar(g):
    g.set_boundary(g.vertices())
    return g.is_circular_planar(ordered=False,set_pos=True)

outerplanar_2trees=dict()
outerplanar_2trees[2]=[graphs.CompleteGraph(2)]

final_order=12
for order in [3..final_order]:
    new_graphs=[]
    for g in outerplanar_2trees[order-1]:
        new_vertex=order
        g=g.copy() # Copy so that we don't modify the graph in the list we already made
        g.add_vertex(new_vertex)
        for e in g.edges():
            h=g.copy() # Copy so that we can add edges to the new vertex
            h.add_edges([(e[0],new_vertex),(e[1],new_vertex)])
            new_graphs.append(h)
    # Now we need to make the list of graphs unique.
    # We do this by asking for a canonical labeling, then a string representation of that labeling
    # We then put these into a set, so that we ignore duplicates
    # This effectively gets us a list of nonisomorphic graphs
    new_graphs_strings=set([j.canonical_label().graph6_string() for j in new_graphs])
    new_graphs_nonisomorphic=[Graph(s) for s in new_graphs_strings]
    # Now just store the outerplanar graphs
    outerplanar_2trees[order]=[g for g in new_graphs_nonisomorphic if is_outer_planar(g)]
    print "Found %s outerplanar 2-trees of order %s"%(len(outerplanar_2trees[order]), order)

Found 1 outerplanar 2-trees of order 3 Found 1 outerplanar 2-trees of order 4 Found 1 outerplanar 2-trees of order 5 Found 3 outerplanar 2-trees of order 6 Found 4 outerplanar 2-trees of order 7 Found 12 outerplanar 2-trees of order 8 Found 27 outerplanar 2-trees of order 9 Found 82 outerplanar 2-trees of order 10 Found 228 outerplanar 2-trees of order 11 Found 733 outerplanar 2-trees of order 12

show(outerplanar_2trees[2])

show(outerplanar_2trees[3])

show(outerplanar_2trees[4])

show(outerplanar_2trees[5])

show(outerplanar_2trees[6])

show(outerplanar_2trees[7])

show(outerplanar_2trees[8])

show(outerplanar_2trees[9])

Now let's draw the graphs so that the outerplanar structure is visible (this will also make the 2-tree structure visible).

for g in outerplanar_2trees[6]:
    g.set_boundary(g.vertices())
    a=g.is_circular_planar(ordered=False,set_pos=True)
    show(g.plot()+text(g.graph6_string(),(-1.1,-1.1)), axes_pad=.1,axes=False)

for g in outerplanar_2trees[7]:
    g.set_boundary(g.vertices())
    a=g.is_circular_planar(ordered=False,set_pos=True)
    show(g.plot()+text(g.graph6_string(),(-1.1,-1.1)), axes_pad=.1,axes=False)

for g in outerplanar_2trees[8]:
    g.set_boundary(g.vertices())
    a=g.is_circular_planar(ordered=False,set_pos=True)
    show(g.plot()+text(g.graph6_string(),(-1.1,-1.1)), axes_pad=.1,axes=False)

for g in outerplanar_2trees[9]:
    g.set_boundary(g.vertices())
    a=g.is_circular_planar(ordered=False,set_pos=True)
    show(g.plot()+text(g.graph6_string(),(-1.1,-1.1)), axes_pad=.1,axes=False)