6
$\begingroup$

I have a certain kind of graphs. They are DAGs similar to dependency graphs but strictly hierarchical, that is, each node belong to a certain level in the hierarchy and cannot be moved up or down when the graph is laid out onto a plane. The nodes can be arbitrarily exchanged with others in the same level.

Here's an example:

The Problem

The problem:

Find an ordering (permutation) of the nodes in each level of the hierarchy such that the total number of edge crossings is minimal.

The problem could be, I suppose, rephrased as a decision problem: Given an ordering of nodes in each level, decide whether that ordering is minimal in terms of number of edge crossings.

For example, in the above graph embedding there are 3 edge crossings, however, by reordering the nodes in a certain way we obtain an embedding that only has 1 edge crossing (I believe this is minimum for this particular graph):

The problem - solution

(Nodes that have been moved are highlighted.)

The question:

Is this problem NP-hard? I'm having a hard time finding correspondence to one of the more well-known NP-hard/NP-complete problems but at the same time I'm having a hard time finding a polytime solution.

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ What specifically have you tried? Where did you get stuck? $\endgroup$
    – Raphael
    Commented Jun 9, 2017 at 11:32
  • 1
    $\begingroup$ First thing I tried was adapting the Sugiyama approach (that was quite some time ago and I do remember the specific details today) and then variants of force-directed layouting. Both of these methods unfortunatelly are usually only able to find a local minimum which may be quite far from the global one. Recently I looked into planarity testing, specifically Tremaux trees, whether that would somehow be beneficial. There are common features to both problems, but the planarity one is more restricted and so I couldn't really apply that here. $\endgroup$
    – kralyk
    Commented Jun 9, 2017 at 12:16
  • 1
    $\begingroup$ Next I'm planning to look into exact cover problem, that seems to be sortof kindof in the same vein, specifically, seems like plynomio solving algorithms might be relevant. I've yet to do that. As for proving NP-hardness, I haven't found a problem similar enough to reduce to mine, but I'm not very good at that so it's probably just me. $\endgroup$
    – kralyk
    Commented Jun 9, 2017 at 12:19
  • 1
    $\begingroup$ To be clear, in the resulting graph drawing, the vertices in each level of the graph must be on a straight line, and the lines for the different rows must be parallel? But the vertices at a particular level don't have to be equally spaced, so it's more than just a permutation that you're looking for, right? $\endgroup$
    – David Richerby
    Commented Jun 9, 2017 at 20:20
  • 1
    $\begingroup$ @DavidRicherby That's right. $\endgroup$
    – kralyk
    Commented Jun 9, 2017 at 20:30

1 Answer 1

Reset to default
4
$\begingroup$

Turns out this is indeed an NP-complete/NP-hard problem according to wikipedia and Eades et al.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ The NP-hardness applies even when there are only two layers, so the number of layers being small doesn't qualitatively help. ​ On the other hand, when the layers themselves are all small, this can be solved efficiently by dynamic programming, one layer at a time. ​ ​ ​ ​ $\endgroup$
    – user12859
    Commented Sep 1, 2017 at 2:04
  • $\begingroup$ @RickyDemer I know the general idea of dynamic programming and some applications, but it's unclear to me how it would be applied in this case. Can you be more specific? $\endgroup$
    – kralyk
    Commented Sep 1, 2017 at 13:06
  • 1
    $\begingroup$ For all permutations of the top layer, the minimum number of crossings above that layer with that permutation is zero (since there are no edges above the top layer). ​ For each other layer L and each permutation of that layer, the minimum number of crossings above L is the minimum, taken over the permutations of the layer L' that is just above L, of [[the number of crossings between L and L' with their permutations] plus [the minimum number of crossings above L' with that layer's permutations]]. ​ ​ ​ ​ $\endgroup$
    – user12859
    Commented Sep 1, 2017 at 19:04
  • $\begingroup$ @RickyDemer Ah, ok, that's interesting. Thanks! $\endgroup$
    – kralyk
    Commented Sep 2, 2017 at 16:28

Your Answer

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

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