Segment crossing algorithm 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 ?

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.
