graphics - Arranging connector lines

Heike gave an absolutely wonderful answer to my question about arranging subplots around a main plot and including connector lines. This is the result:

Starting from Heike's answer, what is the best order to arrange the subplots in so the connector lines are as easy to follow / as aesthetically arranged as possible?

To have something concrete to test with, let's say we have 12 points in the unit square. These are the starting points of the lines.

start = RandomReal[1, {12, 2}];

The set of endpoints is fixed (due to the subplot positions):

end = With[{dx = 0.1, dy = 0.1}, 

       {{-dx, 1 + dy}, {.25 - dx/4, 1 + dy}, {.75 + dx/4, 1 + dy}, 
        {1 + dx, 1 + dy}, {1 + dx, .75 + dy/4}, {1 + dx, .25 - dx/4}, 
        {1 + dx, -dy}, {.75 + dx/4, -dy}, {.25 - dx/4, -dy}, 
        {-dx, -dy}, {-dx, .25 - dy/4}, {-dx, .75 + dy/4}}];

Then the plot will look similar to this:

Graphics[{
  FaceForm[Lighter@Orange], Polygon[{{0, 0}, {1, 0}, {1, 1}, {0, 1}}],
  Line@Transpose[{start, end}],
  AbsolutePointSize[18], Lighter@Orange, Point[end], 

  Black, MapThread[Text, {Range[12], end}]}, 
  Frame -> True, FrameTicks -> None, PlotRange -> {{-.2, 1.2}, {-.2, 1.2}}]

Given the starting points in the orange square, how can we automatically reorder the labelled endpoints so the lines cross as little as possible (or generally: the figure looks as good as possible)?

Please try to make your answers complete, with a sample output figure using the code above. When it is not possible to avoid that the lines cross, what the "best" arrangement is is admittedly somewhat subjective.

---

Note: This is a question that I thought others would be interested in too. It is not a practical problem I am facing (I ordered the subplots manually in my figure), but of course if there are any good solutions, I will use them. I will be working on solutions as well.

Note 2: Given two lists, l1 and l2, containing the same elements in different orders, the permutation that re-orders l1 to l2 is Part[Ordering[l1], Ordering@Ordering[l2]]. This may be useful for reordering points.

Answer

This method tries to find a minimum of the total length of all connecting lines by repeatedly swapping the endpoints of pairs of connecting lines if that reduces the total length of those two connecting lines until the list of edges doesn't change anymore. From the triangle inequality this then also guarantees that no two connecting lines will intersect each other.

start = RandomReal[1, {12, 2}];
end = With[{dx = 0.1, dy = 0.1}, 
       {{-dx, 1 + dy}, {.25 - dx/4, 1 + dy}, {.75 + dx/4, 1 + dy}, 
        {1 + dx, 1 + dy}, {1 + dx, .75 + dy/4}, {1 + dx, .25 - dx/4}, 
        {1 + dx, -dy}, {.75 + dx/4, -dy}, {.25 - dx/4, -dy}, 
        {-dx, -dy}, {-dx, .25 - dy/4}, {-dx, .75 + dy/4}}];

combis = Subsets[Range[12], {2}];
length[{b_, e_}] := EuclideanDistance[start[[b]], end[[e]]]


newedges = Transpose[{Range[12], Range[12]}];
FixedPoint[
 Do[p = {#[[{1, 4}]], #[[{3, 2}]]} &@Flatten[newedges[[c]]];
   If[Total[length /@ p] < Total[length /@ newedges[[c]]],
    newedges[[c]] = p],
   {c, combis}] &, newedges, 10]

Then the before picture is this:

and the after picture is:

Graphics[{FaceForm[Lighter@Orange], 
  Polygon[{{0, 0}, {1, 0}, {1, 1}, {0, 1}}], 
  Line@Transpose[{start[[newedges[[All, 1]]]],
     end[[newedges[[All, 2]]]]}], AbsolutePointSize[18], 
  Lighter@Orange, Point[end[[newedges[[All, 2]]]]], Black, 
  MapThread[Text, {Range[12], end[[newedges[[All, 2]]]]}]}, 
 Frame -> True, FrameTicks -> None, 
 PlotRange -> {{-.2, 1.2}, {-.2, 1.2}}]