Graph Planarity with Fixed Node Positions

Question

I have an undirected graph with fixed node positions. The nodes cannot be moved, merged, removed or otherwise altered. The edges are fixed to their nodes, but do not have to be straight.

I need to know if it possible to 'bend' or 'draw' the edges such that the graph is planar (i.e. there are no edges crossing).

If such an algorithm or implementation exists, or you just have an idea on how to do it, please let me know!

Erminna

As a quick "upper bound" test, you can simply check whether the graph (ignoring the given locations of vertices within the plane) is planar. If it isn't, you know the answer has to be "no". If it is, you need to investigate further. – Sabbat

Answer 1

This question is answered by "J. Pach and R. Wenger. Embedding planar graphs at fixed vertex locations. Graphs Combin., 17:717–728, 2001" as:

Every planar graph on n vertices admits a planar embedding which maps each vertex to a prespecified distinct location and each edge to a polygonal curve with O(n) bends.
Such an embedding can be constructed in O(n^2) time.

So the answer is that you can construct such a graph if and only if the graph is planar. You can test if a graph is planar in O(n) time according to wikipedia.

Assiut