We've implemented making space in a graph drawing a few years ago where a user would basically say that they want some free space somewhere in an existing drawing and everything else should shift in a way to clear that space, but also to not destroy the drawing too much. One approach I thought about was basically seam carving (apparently coming full circle here), the "global" strategy here: http://live.yworks.com/demos/layout/clearrectanglearea/ ... although sadly it happened to not work out that well in practice and we found better ways of handling that.
