I have used the functions `EdgeDelete` and `EdgeAdd` to expand the graph.
The code generates new vertex names by incrementing the largest vertex name in the graph.

    nextVertexNames[g_] := Max[VertexList[g]] + {{1, 2, 3}, {4, 5, 6}}
    replaceTripod[g_, v_] := Module[{
       oldNeighbors = DeleteCases[VertexComponent[g, v, 1], v], 
       newNeighbors = nextVertexNames[g], go = g
       },
      EdgeAdd[
       EdgeDelete[go, v <-> _],
       Flatten@{
         UndirectedEdge[v, #] & /@ First[newNeighbors],
         UndirectedEdge @@@ Partition[Riffle @@ newNeighbors, {2}, 1, 1],
         UndirectedEdge @@@ Thread[{Last@newNeighbors, oldNeighbors}]}
       ]
      ]
    replaceTripods[g_] := 
      Fold[replaceTripod, g, 
       Extract[VertexList[g], Position[VertexDegree[g], 3]]];

For your case, use `replaceTripods[g]` to replace all tripods in the graph `g`. 

**Update**
As kindly suggested by *halmir* below, the resulting graph can be displayed just as in your example using the option `GraphLayout -> "TutteEmbedding"`.

    g = Graph[{1 <-> 2, 1 <-> 3, 1 <-> 4, 2 <-> 3, 2 <-> 4, 3 <-> 4}, 
       VertexLabels -> "Name", GraphLayout -> "TutteEmbedding"];
    replaceTripods[g]

[![enter image description here][1]][1]


  [1]: http://i.stack.imgur.com/0sOvD.png