welcome: please sign in
location: FinalProblemDescriptions / CrossingMinimization

Crossing minimization in layered graphs

Problem Description

The standard approach for drawing hierarchical network diagrams is a three phase approach in which

  1. nodes in the graph are assigned levels producing a k-level graph;

  2. nodes are assigned an order so as to minimize edge crossings in the k-level graph; and

  3. the edge routes and node positions are computed.

There has been considerable research into step 2 which is called k-level crossing minimization. Unfortunately this step is NP-hard for even two layers (k = 2) where the ordering on one layer is given. Thus, research has focussed on developing heuristics to solve it. In practice the approach is to iterate through the levels, re-ordering the nodes on each level using heuristic techniques such as the barycentric method. Recently it was shown that modern optimization technology can tackle the complete k-level crossing minimization problem at least for small to medium sized graphs, generating optimal crossings.

A crossing in a graph occurs if there are:

  1. nodes N1, N2 on layer i, and
  2. nodes N3, N4 on layer j, (j <> i), and

  3. edges e1 = (N1,N3), e2 = (N2,N4), and
  4. the position of N1 is antecedent of the position of N2, and
  5. the position of N4 is antecedent of the position of N3.


Input format

The predicates layers/1 and in_layer/2 give the partitioning of nodes into layers. For convenience, width/2 gives the number of nodes in a layer. For example

layers(2). width(0, 2). in_layer(0,n1). in_layer(0,n2). width(1, 1). in_layer(1,n3).

defines two layers, layer 0 containing nodes {n1, n2} and layer 1 containing {n3}.

The predicate edge/2 defines edges between nodes. For example

edge(n1,n3). edge(n2,n3).

Output format

A solution to the problem is an assignment of each node to a position in its layer, which minimizes the number of crossings in the graph. This is given by the position/2 predicate, where position(n,3) assigns node 'n' to the third position in its layer. Positions at a layer L are numbered from 1 until the width of L.



layers(2). width(0, 2). in_layer(0,n1). in_layer(0,n2). width(1, 1). in_layer(1,n3). edge(n1,n3). edge(n2,n3).

Possible output:

position(n1,1). position(n2,2). position(n3,1).

Additional sample instances: download

Problem Peculiarities

Type: Optimization Competition: Both

This problem is considered quite hard in practice, and is usually approached using ad-hoc heuristics. The instance family is based on graphs taken from the graphviz website and randomly generated layered graphs of known optimal value. The outcomes of this benchmark will give a clear idea of the gap-width of declarative technologies in this respect.

Notes and updates


ASP Competition 2013: FinalProblemDescriptions/CrossingMinimization (last edited 2013-02-01 11:31:39 by CarmineDodaro)