Drawing a graph with vertex avoiding edges? (Handling vertices that must be colinear?)

Question

I'd like to draw something like the following graph:

testGraph = Graph[{1 \[UndirectedEdge] 2, 1 \[UndirectedEdge] 4,
                   2 \[UndirectedEdge] 3, 2 \[UndirectedEdge] 5,
                   3 \[UndirectedEdge] 4}, 
                   VertexLabels -> {1 -> "1", 2 -> "2", 3 -> "3", 4 -> "4", 5 -> "5"}, 
                   VertexCoordinates -> {{0, 0}, {1, 1}, {2, 3}, {4, 1}, {3, 3}}, 
                   ImagePadding -> 10]

However, without changing any of the explicitly specified vertex positions, I'd like edges to curve to avoid vertices. For example, while it's fine that the edges between vertices 2 and 5, and 3 and 4 cross, what if I have an edge between vertices 1 & 5 (if I actually do this, Mathematica v9 appears to no longer respect my vertex coordinates) and what if I would like this edge not to pass through a small sphere about vertex 2?

Is there any way to enforce vertex positionings while allowing for curved edges that avoid vertices in Mathematica v9? This is a dream, however, could I specify a length for an edge and have it travel along an arc to meet that length requirement provided stationary vertices?

A hack would involve creating a set of edges between "invisible" vertices, however, it would take a lot of invisible vertices to create an appropriate curvature effect, and this doesn't seem like the right thing to do.

Answer 1

quick fix is to use EdgeShapeFunction. My function here is not very sophisticated so it may happen that you cross different vertices somewhere some day, so be careful :) :

 Graph[{1 \[UndirectedEdge] 2, 1 \[UndirectedEdge] 4, 2 \[UndirectedEdge] 3,
        2 \[UndirectedEdge] 5, 1 \[UndirectedEdge] 5, 3 \[UndirectedEdge] 4}, 
  VertexLabels -> {1 -> "1", 2 -> "2", 3 -> "3", 4 -> "4", 5 -> "5"}, 
  VertexCoordinates -> {{0, 0}, {1, 1}, {2, 3}, {4, 1}, {3, 3}}, 
  ImagePadding -> 10, 
  EdgeShapeFunction -> (BezierCurve[
                          {#, # + .5 RotationMatrix[.3].(#2 - #), #2} & @@ #] &)]

Answer 2

Update: The edge shape function "CurvedArc" has an option "Curvature" that controls the shape of the BezierCurve it produces.

Examples:

Graph[{1 -> 2, 2 -> 3, 1->3}, VertexCoordinates -> {{0, 0}, {1, 1}, {2, 2}},
 VertexLabels -> Placed["Name", Center], VertexSize -> Medium,
 EdgeShapeFunction -> GraphElementData[{"CurvedArc", "Curvature" -> 2}]]

Graph[{1 -> 2, 2 -> 3}, VertexCoordinates -> {{0, 0}, {1, 1}, {2, 2}},
 VertexLabels -> Placed["Name", Center], VertexSize -> Medium,
 EdgeShapeFunction -> {(1 -> 2) -> GraphElementData[{"CurvedArc", "Curvature" -> 1}],
   (2 -> 3) -> GraphElementData[{"CurvedArc", "Curvature" -> -2}]}]

gr = Graph[{1 -> 2, 1 -> 4, 2 -> 3, 2 -> 5, 3 -> 4, 1 -> 5},
   ImagePadding -> 10, VertexCoordinates -> {{0, 0}, {1, 1}, {2, 3}, {4, 1}, {3, 3}},
   VertexLabels -> Placed["Name", Center], VertexSize -> Medium,  ImageSize -> 500];

gr2 = Fold[SetProperty[{#, #2[[1]]},
     {EdgeLabels -> Placed[Style["curvature\n" <> ToString[#2[[2]]], 14],  "Middle"], 
      EdgeShapeFunction -> Composition[Style[#, Arrowheads[{{Large, .75}}]] &,
        Arrow, GraphElementData[{"CurvedArc", "Curvature" -> #2[[2]]}]]}] &,
   gr, {{1 -> 4, 1.}, {2 -> 5, 0.}, {1 -> 5, .75}, {3 -> 4, -2.5}}];

Row[{gr, gr2}]

---

Original post:

There is a built-in EdgeShapeFunction, "CurvedArc", that produces a set of edges that look almost exactly like the ones in @Kuba's answer.

SetProperty[testGraph, EdgeShapeFunction -> "CurvedArc"]

testGraph2 = EdgeAdd[testGraph, 1 -> 5];
SetProperty[testGraph2, EdgeShapeFunction -> "CurvedArc"]

Curve only the edges 1 -> 4, 2 -> 5, and 1 -> 5:

Fold[SetProperty[{#, #2}, EdgeShapeFunction -> "CurvedArc"] &, testGraph2, 
    {1 -> 4, 2 -> 5, 1 -> 5}]

Answer 3

There is the somewhat hidden built-in graph-method of "EdgeLayout" that can be exploited for this purpose (see Details under GraphLayout):

AdjacencyGraph[Range@8, Table[Boole[j > i], {i, 8}, {j, 8}],
   DirectedEdges -> True, VertexLabels -> "Name",
   GraphLayout -> {
     "EdgeLayout" -> {"DividedEdgeBundling", 
       "CoulombConstant" -> #[[1]], "VelocityDamping" -> .2, 
       "SmoothEdge" -> True,
       "NewForce" -> False, "Connectivity" -> True, 
       "Compatibility" -> #[[3]], "Threshold" -> #[[4]], 
       "CoulombDecay" -> 1, "LaneWidth" -> #[[2]]}, 
     "VertexLayout" -> {"MultipartiteEmbedding", 
       "VertexPartition" -> {1, 3, 3, 1}}
     }, PlotLabel -> #] & /@ {
        {0, 0, True, .1}, {-10, 100, True, .1}, {-100, .1, True, .1},
        {10, .1, True, .1}, {100, .1, True, .1}, {100, 10, False, .1},
        {500, .1, True, .01}, {-10, 100, False, .1}, {-100, .1, False, .1},
        {100, .1, True, .5}}