= Crossing minimization in layered graphs = <> == Problem Description == The standard approach for drawing hierarchical network diagrams is a three phase approach in which (a) nodes in the graph are assigned levels producing a k-level graph; (b) nodes are assigned an order so as to minimize edge crossings in the k-level graph; and (c) the edge routes and node positions are computed. There has been considerable research into step (b) which is ccalled 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. == Predicates == * '''Input''': {{{layers/1, width/2, in_layer/2, edge/2}}} * '''Output''': {{{position/2}}} == 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. == Author(s) == * Author: Peter Stuckey * Affiliation: University of Melbourne, Australia * Author: Graeme Gange * Affiliation: University of Melbourne, Australia