Given an embedding of a graph (with that I mean a concrete spacial layout of the graph on the 2D plane with only $n$ straight edges. Is this the right terminology?), how can I determine if that embedding is planar?
Just for clarification, this would be a planar embedding:
while this would not be a planar embedding:
The graph itself is of course planar both times, but since AD and BC cross in the second embedding, that embedding is not planar.
A simple solution would of course be to test if any of the edges intersect, but that is an $O(n^2)$ operation, which may be too slow for my purposes. Since there are algorithms for determining if a graph is planar in linear time, I hoped that there would also be algorithms for determining if an embedding is planar (since that seems like an easier problem), but all algorithms I can find are either used to draw an embedding, generate an embedding, or check if a graph is planar.
I am not interested in creating a planar embedding, I need to determine if a given embedding is planar. It would also be useful if the algorithm could determine which edges violate the planarity, but that is not a requirement.
Best Answer
The sweep line algorithm sounds like what you need.