It seems to me that the easiest way to do this would be in two steps:
Suppose we start with this situation:

Look at that glorious programmer art. I've chose red and green for the node colors because it makes things a bit more visible.
Think of it like a balloon. First we wrap it around the nodes as tight as possible, and then we'll blow it up as much as it will allow.
We want to create a conbex polygon around all the edges. So we start at an arbitrary node, let's say the one at the top-left.
- Starting at the top-left corner on the first node, we move around it in a clockwise fashion, towards the node in the top-center.
- When the distance between the points on the first node with the center of the second node becomes greater instead of smaller, we jump to the next node.
- The next node is never the node we came from, unless we've reached the last node. In that case, we traverse the node graph in reverse order.
This is a very basic algorithm, but it works. Here's what you should end up with:

Unfortunately, this polygon is too thin. Lines have collapsed onto each other. So let's expand the polygon with a new algorithm.
- Store the original convex polygon we made.
- For every line segment, try creating a new line segment to the next point in sequence if that's valid. For example, instead of a line segment
{Node1, point2}{Node1, point3}
, create a line segment {Node1, point2}{Node2,point1}
- Create a new convex polygon using this line segment.
- Check if a green node falls within this new convex polygon.
- If it doesn't, use this convex polygon from now on.
- Use a fitness function to determine whether the line segment is better or worse than the old line segment. An example could be: greatest distance between points.
- Stop iterating for this point when the fitness function returns a worse value.
What you should now end up with is this:

This algorithm isn't perfect and still needs work, but it should give you a start.
P.S.: I spent over an hour on this problem, it was extremely interesting to solve!