algorithm - Connect an even number of nodes without intersection -

i have 2 sets of n nodes. want connect each node 1 set node other set. resulting graph should have no intersections.

i know of several sweep line algorithms (bentley-ottmann-algorithm check intersections occur, couldn't find algorithm solve intersections, except brute-force approach.

each node 1 set can connected other node within other set.

any pointers (an efficient) algorithm solves problem? no implementation needed.

edit1:

here 1 solution problem n=7:

the black dots set of nodes , red dotes set. each black node has connected 1 red node lines connecting them not crossing.

edit2:

to further clarify: positions of nodes fixed , resulting graph have n edges. don't have proof solution exists, couldn't create example there no solution. i'm sure there proof out there somewhere creating such planar graph possible. also, one solution needed, not possible solutions.

when solution exists (see comment giving example instance not), can found finding minimum weight matching in complete bipartite graph contains (red or black) vertex every point, , every red vertex u , black vertex v, edge (u, v) of weight equal euclidean distance between corresponding points. can solved optimally in o(v^4) time.

why should work? main idea, took david eisenstat's answer similar question, whenever have pair of line segments ab , cd intersect @ point x, triangle inequality can used show picking either endpoint of each , swapping them gives pair of line segments lower or equal total length:

a |\ | \ |  \ x c---+-----d      \   /       \ /        b  ax + xc >= ac (tri. ineq.) bx + xd >= bd (tri. ineq.) ax + xc + bx + xd >= ac + bd (sum both sides) (ax + bx) + (xc + xd) >= ac + bc (rearrange lhs)    ab     +    cd     >= ac + bc (combine pairs of segments on lhs) 

assuming further triangles axc , bxc non-degenerate, >= becomes >. (a sufficient condition no set of 3 points containing @ least 1 red , 1 black point collinear.) so, given solution (assignment of red nodes black nodes), if solution contains crossing, total sum of line segment lengths can reduced nonzero amount swapping red (or black) endpoints of 2 crossing line segments.

in other words,

solution contains crossing => sum of segment lengths not minimal. 

taking contrapositive, get

sum of segment lengths minimal => solution contains no crossing. 

since minimum weight matching algorithm returns solution of minimum possible weight, establishes correctness.

(notice it's not necessary worry whether or not endpoint-swapping guarantees new pair of line segments ac , bc don't intersect -- while seems obvious won't, need proof of correctness show crossing exists => sum not minimal.)