welcome: please sign in

Upload page content

You can upload content for the page named below. If you change the page name, you can also upload content for another page. If the page name is empty, we derive the page name from the file name.

File to load page content from
Page name
Comment

Revision 6 as of 2011-01-20 11:05:23

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