I have a connected graph in 2D plane composed of some vertices and some edges defined between them. The overall shape of the graph is not necessarily convex, i.e. the adjacent vertices on the convex hull are not always connected by an edge. Now is there an existing algorithm that finds the 'outline' of this graph? The issue that's troubling me the most is that this outline polygon may contain vertices that are not vertices in the original graph, but rather the intersection of two edges, so I'm not quite sure how to deal with it...
Thanks!
Niko