How to reduce the number of crossing edges in a diagram?

Question

I am working on a diagram editor. Diagrams display 2D shapes (nodes) connected with connectors (edges).

I'd like to add an operation that, given a selection of nodes, "disentangles" them: it repositions them to minimize the number of crossing edges, if possible (and it's OK if the edges will have to be drawn with bend points).

So I want a graph algorithm that, given a (topological) graph embedding and a subset of its nodes, modifies the embedding (its topology) on only those nodes so as to minimize the number of crossing edges.

From reading about apex graphs and browsing Cabello and Mohar (2013), I suppose this problem is NP-hard. So I'll be happy with a parametrized algorithm (e.g. on the number of crossing edges) that has a known, polynomial, time complexity for any given parameter value. This seems feasible, but I don't find it easy to come up with such an algorithm on my own.

Questions:

• Where do I look for such an algorithm?
• Does it exist?
• In existing software?
• Is there any significant practical experience with such an operation? (What looks good in theory may not be so good in practice, or vice versa.)

(I am not sure where best to ask this question: here, on StackOverflow, or MathOverflow?)

Answer 1

Computing the absolute minimal crossing number is, as you observed, $\text{NP-hard}$. The process of drawing the graphs should be at least as hard as that.

The problem posed in the question is actually harder and more involved than the above. You are considering graph nodes of a certain size and shape while also bounding the size (area) of the result. In addition, a not yet determined notion of aesthetics is desired. Obviously we want a heuristic for this, which does not use the absolute minimum in the general case. The number of nodes encountered in such an application are likely not huge in the average case. Drawing the minimal edge crossing version of the graph may be feasible for small sizes.

Resources:
You may be interested in the following resources, particularly with the first:

• The documentation for a feature of the Graphviz package presents an algorithm that generates nice looking directed graphs: http://www.graphviz.org/Documentation/TSE93.pdf
  It has multiple other features that may prove useful. The source code is located on their website under EPL. It also includes a page dedicate to the theory behind graph visualization.
• For a fixed-parameter algorithm check a paper by Martin Grohe:
  Computing Crossing Numbers in Quadratic Time
• A tech talk given by Amina Shabbeer at RPI:
  Preserving Proximity Relations and Minimizing Edge-crossings in Graph Embeddings
• An example of an efficient probabilistic algorithm can be found in this paper by Julia Chuzhoy:
  An Algorithm for the Graph Crossing Number Problem

There are plenty of other resources, too. These should help you get started.

Additional Thoughts & Observations:

Here is an idea to get around the issues concerning the shape and size of nodes. Given the graph (infinitely small nodes), expand each node while "pushing" or bending edges out of the way (ex. using splines while enforcing a limit on proximity). You need to do this with other edges and nodes that get in the way of it, which can start a chain reaction. Look into how an equilibriums can be efficiently computed (ex. molecular structures). If you cant get the shape of a node to the desired size, then scale the whole diagram.

A user might enjoy the results of a randomized algorithm. They could use your feature multiple times until they got something they liked. Avoid redundant computation in this case (no need to compute a crossing number again).