# Is this graph problem NP-hard / NP-complete?

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:

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

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

• What specifically have you tried? Where did you get stuck? Jun 9, 2017 at 11:32
• 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. Jun 9, 2017 at 12:16
• 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. Jun 9, 2017 at 12:19
• 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? Jun 9, 2017 at 20:20
• @DavidRicherby That's right. Jun 9, 2017 at 20:30