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.
- 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?)