3 replies to this topic

[temelm]

Here is my problem: I have a graph structure (with straight line edges) which I know to be planar (i.e. there exists an embedding of the graph where no edges cross - Planar graph - Wikipedia, the free encyclopedia). I need an algorithm which will take my graph and produce a straight line planar embedding of it. The algorithm does not need to be too efficient (an O(N^2) algorithm would do fine). Any ideas/suggestions?

[WingedPanther]

I'd want to start with how you want to represent the solution. Did you want a set of x/y coordinates for each vertex?

[temelm]

yes, exactly. i can also give you more details about how i represent a graph structure if you like...

[WingedPanther]

The first thing I would do is get untangle here: Simon Tatham's Portable Puzzle Collection Use that to try developing how YOU make a planar graph planar. Once you do that, you will need to write edge cross detection algorithms based on the location of the vertices, then implement your algorithm.