9
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ I would assume the question may be better suited for StackOverflow, but I did notice that similar questions on there have dissatisfying answers. I'll follow up with an answer that should help you on the theoretical end, but it may be best for your question to be migrated there. $\endgroup$ – mdxn Oct 8 '13 at 18:05
8
$\begingroup$

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:

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

$\endgroup$
  • $\begingroup$ I added topological to my question specifically to avoid the discussion of aesthetics. It's important, but I don't think they affect the basic problem much - I think they can be dealt with in a separate step, after adjusting the topology of the nodes (i.e. which nodes are surrounded by which other nodes). $\endgroup$ – reinierpost Oct 9 '13 at 9:02
  • $\begingroup$ I first used Graphviz over 15 years ago; I use it roughly once per week for all kinds of graphs. I'm not too impressed by its results, and I understand it's hard to do much better. $\endgroup$ – reinierpost Oct 9 '13 at 9:04
  • $\begingroup$ I often visit graphviz.org and I have read some of the papers they refer to. But I haven't yet met an answer to this specific question, and it's not in my job description to become acquainted with the literature. That's why I'm asking it here. $\endgroup$ – reinierpost Oct 9 '13 at 9:11
  • $\begingroup$ Thank you for the references though - I notice this is still current research. $\endgroup$ – reinierpost Oct 9 '13 at 10:11
  • $\begingroup$ The first thing I'll try is a trivial (and therefore not necessarily useful) algorithm roughly based on Ms. Shabbeer's idea. Thanks again. $\endgroup$ – reinierpost Oct 9 '13 at 12:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.