2 Add note about "relies on vertex names being real numbers" edited Aug 9 '15 at 18:29 Patrick Stevens 4,71811 gold badge99 silver badges3434 bronze badges This may or may not do what you want. I don't know about making the layout nice, I'm afraid. The function newvertex returns n names which are not used as a vertex in the graph. Then expandVertex takes a vertex name and expands about that vertex in the manner stated. Alternatively, supply a list of names to have the expansion done on each in turn, or supply no names at all to have every valid vertex expanded in that way. newvertex[g_, n_] := Max@VertexList[g] + Range[n] expandVertex[g_, v_] /; VertexDegree[g, v] != 3 := g expandVertex[g_, v_] := With[{new = newvertex[g, 6]}, With[{r = new[[1]], s = new[[2]], t = new[[3]], st = new[[4]], rs = new[[5]], rt = new[[6]]}, EdgeList[g] /. {xx___, a_ <-> v | v <-> a_, yy___, b_ <-> v | v <-> b_, zz___, d_ <-> v | v <-> d_, aa___} :> {xx, yy, zz, aa, a <-> r, b <-> s, d <-> t, t <-> st, s <-> st, r <-> rs, s <-> rs, r <-> rt, t <-> rt, rt <-> v, st <-> v, rs <-> v}]] // Graph[#Graph[VertexList[g], #, VertexLabels -> "Name", GraphLayout -> "PlanarEmbedding"] & expandVertex[g_, v_List] := Fold[expandVertex[#1, #2] &, g, v] expandVertex[g_] := expandVertex[g, VertexList[g]]  Your example would be expandVertex[ic]. It works by a very inefficient pattern match, checking that the input is a vertex of degree 3 and then constructing the appropriate edges. This relies on the vertex names of the graph being integers (or, I suppose, real numbers), I'm afraid. It can be a real pain to work with arbitrary vertex names. This may or may not do what you want. I don't know about making the layout nice, I'm afraid. The function newvertex returns n names which are not used as a vertex in the graph. Then expandVertex takes a vertex name and expands about that vertex in the manner stated. Alternatively, supply a list of names to have the expansion done on each in turn, or supply no names at all to have every valid vertex expanded in that way. newvertex[g_, n_] := Max@VertexList[g] + Range[n] expandVertex[g_, v_] /; VertexDegree[g, v] != 3 := g expandVertex[g_, v_] := With[{new = newvertex[g, 6]}, With[{r = new[[1]], s = new[[2]], t = new[[3]], st = new[[4]], rs = new[[5]], rt = new[[6]]}, EdgeList[g] /. {xx___, a_ <-> v | v <-> a_, yy___, b_ <-> v | v <-> b_, zz___, d_ <-> v | v <-> d_, aa___} :> {xx, yy, zz, aa, a <-> r, b <-> s, d <-> t, t <-> st, s <-> st, r <-> rs, s <-> rs, r <-> rt, t <-> rt, rt <-> v, st <-> v, rs <-> v}]] // Graph[#, VertexLabels -> "Name", GraphLayout -> "PlanarEmbedding"] & expandVertex[g_, v_List] := Fold[expandVertex[#1, #2] &, g, v] expandVertex[g_] := expandVertex[g, VertexList[g]]  Your example would be expandVertex[ic]. It works by a very inefficient pattern match, checking that the input is a vertex of degree 3 and then constructing the appropriate edges. This may or may not do what you want. I don't know about making the layout nice, I'm afraid. The function newvertex returns n names which are not used as a vertex in the graph. Then expandVertex takes a vertex name and expands about that vertex in the manner stated. Alternatively, supply a list of names to have the expansion done on each in turn, or supply no names at all to have every valid vertex expanded in that way. newvertex[g_, n_] := Max@VertexList[g] + Range[n] expandVertex[g_, v_] /; VertexDegree[g, v] != 3 := g expandVertex[g_, v_] := With[{new = newvertex[g, 6]}, With[{r = new[[1]], s = new[[2]], t = new[[3]], st = new[[4]], rs = new[[5]], rt = new[[6]]}, EdgeList[g] /. {xx___, a_ <-> v | v <-> a_, yy___, b_ <-> v | v <-> b_, zz___, d_ <-> v | v <-> d_, aa___} :> {xx, yy, zz, aa, a <-> r, b <-> s, d <-> t, t <-> st, s <-> st, r <-> rs, s <-> rs, r <-> rt, t <-> rt, rt <-> v, st <-> v, rs <-> v}]] // Graph[VertexList[g], #, VertexLabels -> "Name", GraphLayout -> "PlanarEmbedding"] & expandVertex[g_, v_List] := Fold[expandVertex[#1, #2] &, g, v] expandVertex[g_] := expandVertex[g, VertexList[g]]  Your example would be expandVertex[ic]. It works by a very inefficient pattern match, checking that the input is a vertex of degree 3 and then constructing the appropriate edges. This relies on the vertex names of the graph being integers (or, I suppose, real numbers), I'm afraid. It can be a real pain to work with arbitrary vertex names. 1 answered Aug 9 '15 at 18:23 Patrick Stevens 4,71811 gold badge99 silver badges3434 bronze badges This may or may not do what you want. I don't know about making the layout nice, I'm afraid. The function newvertex returns n names which are not used as a vertex in the graph. Then expandVertex takes a vertex name and expands about that vertex in the manner stated. Alternatively, supply a list of names to have the expansion done on each in turn, or supply no names at all to have every valid vertex expanded in that way. newvertex[g_, n_] := Max@VertexList[g] + Range[n] expandVertex[g_, v_] /; VertexDegree[g, v] != 3 := g expandVertex[g_, v_] := With[{new = newvertex[g, 6]}, With[{r = new[[1]], s = new[[2]], t = new[[3]], st = new[[4]], rs = new[[5]], rt = new[[6]]}, EdgeList[g] /. {xx___, a_ <-> v | v <-> a_, yy___, b_ <-> v | v <-> b_, zz___, d_ <-> v | v <-> d_, aa___} :> {xx, yy, zz, aa, a <-> r, b <-> s, d <-> t, t <-> st, s <-> st, r <-> rs, s <-> rs, r <-> rt, t <-> rt, rt <-> v, st <-> v, rs <-> v}]] // Graph[#, VertexLabels -> "Name", GraphLayout -> "PlanarEmbedding"] & expandVertex[g_, v_List] := Fold[expandVertex[#1, #2] &, g, v] expandVertex[g_] := expandVertex[g, VertexList[g]]  Your example would be expandVertex[ic]. It works by a very inefficient pattern match, checking that the input is a vertex of degree 3 and then constructing the appropriate edges.