You’ve got quite hard a problem here.

I’m thinking of a method resembling Sieve of Eratosthenes .

First, you can “name” or “number” each link.
Let’s assume we just have 5 nodes, so we’ll have 10 links. Number each one from 1 until 10.

Now, we can put them all into an array.

Let’s assume we have this list represents two links who intersect each other:

• 1 – 3
• 1 – 4
• 1 – 7
• 1 – 10
• 2 – 4
• 2 – 8
• 3 – 4
• 6 – 9
• 6 – 10

Now let’s visualize this. First, I choose to draw link 1.

*For the images below, green means I choose to draw the link, red means the link cannot be drawn (because it intersects a selected link), and white means the link can be drawn.

Then, check each element from link #2 to link #10: does it intersect link #1? If yes, we should eliminate them (means we must not draw them). In this case : links #3, #4, #7, #10 (from the list above)

Now, you can choose which one is the next to draw: either #2, #5, #6, #8, or #9?
Let’s say you choose #2, then you do the same procedure. Check the rest of the element: If it’s already red then you may skip it, but if it’s white (can still be drawn), check if it intersects link #2. Link #2 intersects with #4 and #8, but since #4 is already eliminated, we just eliminate #8.

Then, pick another link, and so on. Note that we can make use of two arrays: one integer array containing the links, and the other a boolean array to check if it’s eliminated or not.

You can do this in iteration: picking which link to draw and eliminate the ones intersecting them.
This way, you can avoid drawing unnecessary links.

Well, it’s just an idea that might work. But, I neither think this way is easy to implement, nor do I think it can be considered “efficient” in terms of complexity.

To cut down on the count of recursive calls I thought of introducing a strict ordering of links to be able to eliminate duplicates in the initialization phase (before any recursion):

• on the links define any (arbitrary) strict ordering order
• on the links define a method doesNotCrossWith() returning the set of links of higher order which this link does not cross (capable of executing in constant time after initialization)
• on the links define a method doesNotCrossWithIntersectionOf(Set<Link>) returning the intersection of the parameter and doesNotCrossWith()

• define the main recursive method getValidPermutations(Link link, Set<Link> linksNotForbidden) (Pseudocode):

  Plain text

  Copy to clipboard

  Open code in new window

  EnlighterJS 3 Syntax Highlighter

  <code>Set<Set<Link>> validPermutationsIncludingLink;

  // add the current link (alone) itself to the possible permutations (to be added to):

  validPermutations.add(new Set(link));

  Set<Link> linksStillAllowed = link.doesNotCrossWithIntersectionOf(linksAllowed);

  for (Link otherLink : linksStillAllowed) {

  Set<Set<Link>> validPermutationsOfOther;

  //recursive call:

  for (Set<Link> validPermutation : getValidPermutations(otherLink, linksStillAllowed)) {

  validPermutation.add(otherLink);

  validPermutationsOfOther.add(validPermutation);

  }

  validPermutations.addAll(validPermutationsOfOther);

  }

  return validPermutations;

  </code>

  <code>Set<Set<Link>> validPermutationsIncludingLink; // add the current link (alone) itself to the possible permutations (to be added to): validPermutations.add(new Set(link)); Set<Link> linksStillAllowed = link.doesNotCrossWithIntersectionOf(linksAllowed); for (Link otherLink : linksStillAllowed) { Set<Set<Link>> validPermutationsOfOther; //recursive call: for (Set<Link> validPermutation : getValidPermutations(otherLink, linksStillAllowed)) { validPermutation.add(otherLink); validPermutationsOfOther.add(validPermutation); } validPermutations.addAll(validPermutationsOfOther); } return validPermutations; </code>

  Set<Set<Link>> validPermutationsIncludingLink;
  
  // add the current link (alone) itself to the possible permutations (to be added to):
  validPermutations.add(new Set(link));
  
  Set<Link> linksStillAllowed = link.doesNotCrossWithIntersectionOf(linksAllowed);
  
  for (Link otherLink : linksStillAllowed) {
      Set<Set<Link>> validPermutationsOfOther;
  
      //recursive call:
      for (Set<Link> validPermutation : getValidPermutations(otherLink, linksStillAllowed)) {
          validPermutation.add(otherLink);
          validPermutationsOfOther.add(validPermutation);
      }
      validPermutations.addAll(validPermutationsOfOther);
  }
  
  return validPermutations;
  

• call getValidPermutations for each link and build a union of the results.

The maximum recursive depth is the number of (possible) links n.

P.S.: With 7 nodes roughly arranged as in your example I get ~150ms running time with this implementation on my machine resulting in 37055 possible permutations, for a large number of nodes additional optimizations might be needed.