Segment crossing algorithm

Question

I need an ideea of an algorithm to solve a puzzle 'game'. The game is :

• is given N number of line segments by coordinates [(X1n,Y1n),(X2n,Y2n)]
• some of segments have the same ends

We've got something like :

To solve the puzzle we need to move ends of segments in such a way that none of segments intersect (cross), except for ends. The above example solved, looks like :

Does anybody have an idea on how to solve this type of puzzle ?

Answer 1

If the graph is not planar, than there is no solution. If the graph IS planar, there are many solutions, but they are somewhat complicated. See this Wikipedia page.