graph optimization

Is there a well-known method to simplify a nav graph? From what I've seen most people have a nav mesh (made of triangles), not a graph (made of edges). But assume you have a graph - is there a well-known method to remove the edges that wouldn't significantly shorten the paths found on the graph? I wonder if this is a well-known problem (I don't know what to search for on google - "graph simplification" turns up a bunch of weird topology papers).

I wrote up a little solution for it that I think works pretty well. Here's my sweet-ass visualization: http://i.imgur.com/XMOaM.png
It's a graph made of random edges in 3d. Black lines were rejected from the original graph, white lines were kept in the simplified graph.

The method is to keep candidate edges from the original graph only when they're shorter than some fraction of the shortest existing path between those vertices. Like building a minimum spanning tree, visit the candidates in length order.

The tricky part is you need to know those shortest path lengths (for all pairs of verts in the graph as they're added). To do that, you can propagate shortest-path updates each time you add an edge (a newly shortened path AB adds new potential shortened paths from A to each of B's neighbors and from B to each of A's neighbors too).

All paths in the shrunk graph are guaranteed to be within an arbitrary threshold of optimal. (if the threshold is small, you get a minimum spanning tree, which is neat!). In the picture, it's a <2x optimal path length guarantee.

Performance is weird, something like O(#verts * #edges)? The shortest-path-update ordering (stack vs. queue for the to-visit list) has a huge impact on performance and I'm not really sure why :o It handles graphs up to about 500-1000 edges instantly, but barfs on bigger inputs. The aspect that could be improved is the shortest path propogation - depending on the edge add order, a lot of the path shrinking is wasted effort.

I think a further improvement would be start with the minimum spanning tree (which is decently fast), compute the all-pairs shortest paths, then start adding the remaining candidate edges. This skips the majority of the shortest-path updating, since the graph is mostly connected.

Let me know if you want me to post the code somewhere, it's pretty simple.