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 called k-level crossing minimization. Unfortunately this step is NP-hard even for 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.

The problem sets will be based on graphs taken from the graphviz website and randomly generated layered graphs. In all cases the true optimal is known so that can be used to judge entries.

Input format

Output format

Example

Author(s)

Author: Peter Stuckey and Graeme Gange
Affiliation: