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.