13
$\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 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?)

$\endgroup$
3
  • 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, 2013 at 18:05
  • 1
    $\begingroup$ There is very in-depth work being done here: complang.tuwien.ac.at/cd/ebner/ebner05da.pdf $\endgroup$
    – Dschoni
    Mar 5, 2020 at 13:53
  • $\begingroup$ Thanks! Not only that, but it is clearly a very readable presentation of the problem and a survey of some well-known approaches. $\endgroup$ Mar 5, 2020 at 15:46

1 Answer 1

11
$\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$
7
  • $\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$ Oct 9, 2013 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$ Oct 9, 2013 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$ Oct 9, 2013 at 9:11
  • $\begingroup$ Thank you for the references though - I notice this is still current research. $\endgroup$ Oct 9, 2013 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$ Oct 9, 2013 at 12:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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