Vertex hides point where edges cross - how to move vertex?

g = Graph[{a <-> 1, a <-> 2, a <-> 3, a <-> 4, b <-> 5, b <-> 6, 
   b <-> 7, b <-> 8, c <-> 9, c <-> 10, c <-> 11, c <-> 12, d <-> 13, 
   d <-> 14, d <-> 15, d <-> 16, a <-> b, a <-> c, a <-> d, b <-> c, 
   b <-> d, c <-> d, 1 <-> i, 2 <-> j, 3 <-> k, 4 <-> l, 5 <-> m, 
   6 <-> n, 7 <-> o, 8 <-> p, 9 <-> q, 10 <-> r, 11 <-> s, 12 <-> t, 
   13 <-> u, 14 <-> v, 15 <-> w, 16 <-> x, a <-> M, b <-> M, c <-> M, 
   d <-> M}, VertexLabels -> "Name"]

SetProperty[{g, M}, VertexCoordinates -> {2.45, 2.8}]

Or like rasher noted you can play with GraphLayout but It's pretty ugly IMO (GraphLayout -> "DiscreteSpiralEmbedding" below):

An alternative approach is to keep the vertex coordinates and change the edge shapes:

g1 = Graph[{a <-> 1, a <-> 2, a <-> 3, a <-> 4, b <-> 5, b <-> 6, 
    b <-> 7, b <-> 8, c <-> 9, c <-> 10, c <-> 11, c <-> 12, d <-> 13,
    d <-> 14, d <-> 15, d <-> 16, a <-> b, a <-> c, a <-> d, b <-> c,
    b <-> d, c <-> d, 1 <-> i, 2 <-> j, 3 <-> k, 4 <-> l, 5 <-> m, 
    6 <-> n, 7 <-> o, 8 <-> p, 9 <-> q, 10 <-> r, 11 <-> s, 12 <-> t, 
    13 <-> u, 14 <-> v, 15 <-> w, 16 <-> x, a <-> M, b <-> M, c <-> M,
    d <-> M}, VertexLabels -> "Name",  ImagePadding -> 10, ImageSize -> 360];

g2 = SetProperty[g1, EdgeShapeFunction -> (_ <-> M | c <-> d | b <-> a -> 
       GraphElementData[{"CurvedArc", "Curvature" -> 1/2}])];

Row[{g1, g2}]

Alternatively, just change the two edges or all edges:

g3 = SetProperty[g1, 
    EdgeShapeFunction -> (c <-> d | b <-> a -> {"CurvedArc",  "Curvature" -> 1/2})];
g4 = SetProperty[g1, 
   EdgeShapeFunction -> {"CurvedArc", "Curvature" -> 1/2}];
Row[{g3, g4}]