# Theoretical Computer Science / Theoretische Informatik

Institut[e] f(o|ü)r Informati(cs|k), [Universität] Osnabrück [University]

# Multi-Level Vertical Ordering / Verticality Optimization

Here, you can find the benchmark sets used in our study of heuristics, as well as, linear, quadratic, and semidefinite programs to solve Multi-level Verticality Optimization problems. Detailed descriptions can be found in the papers:

## Instances

Description File
MLVO, Proper level graphs, narrow alignment scheme mlvm.proper.narrow.tar.gz
MLVO, Proper level graphs, wide alignment scheme mlvm.proper.wide.tar.gz
MLVO, Non-proper level graphs, narrow alignment scheme mlvm.nonproper.narrow.tar.gz
MLVO, Non-proper level graphs, wide alignment scheme mlvm.nonproper.wide.tar.gz
MLCVO (hence: Proper level graphs, narrow alignment scheme) mlcvo.tar.gz

Each package contains all the instances of the groups Polytope, Graphviz, and Other. The node order given in these files is the order of the optimal (or best known) solution, as reported in the paper. You may also be interested in corresponding multi-level crossing minimization results.

Rome graphs and North DAGs instances: identical to the ones of the MLCM study.

## Generating Drawings

You may want to use (free for private and academic use, no liability!) the the following python-scripts to generate SVGs from the raw solution files.

• mlvo2svg_p.py generates the directly induced drawing of a proper level graph (cf. also file format below).
• mlvo2svg_np.py and mlvo2svg_np_inverted.py use the drawing algorithm sketched in the above technical report TR-FSUJ-CS-AE-11-01. The latter script uses inverted logic, i.e., bundles the edges with same sink, instead of same source.

## File Format

The package-files contain simple text files, each text file is a single instance.

For proper level graphs, the format is as follows:

  <Number-of-Levels>
<Number-of-Edges-Between-First-and-Second-Level>
<Number-of-Edges-Between-Second-and-Third-Level>
...
<Number-of-Nodes-on-First-Level> <Type-of-Node-0> <Type-of-Node-1> <Type-of-Node-2> ...
<Number-of-Nodes-on-Second-Level> <Type-of-Node-0> <Type-of-Node-1> <Type-of-Node-2> ...
...
<Index-of-Node-on-First-Level> <Index-of-Node-on-Second-Level>
<Index-of-Node-on-First-Level> <Index-of-Node-on-Second-Level>
...
<Index-of-Node-on-Second-Level> <Index-of-Node-on-Third-Level>
...

Thereby, the 2-tuples describe the edges in the graph. The node indices start with 0 on each layer. A node is either of type "1" (original node), "0" (positional dummy) or "-1" (long-edge dummy).

For non-proper level graphs, the format is as follows:

  <Number-of-Levels>
<Number-of-Edges>
<Number-of-Nodes-on-First-Level>
<Number-of-Nodes-on-Second-Level>
...
<Index-of-Node> <Index-of-Node>
...

Thereby, the 2-tuples describe the edges in the graph. The node indices, starting with 0 on the first layer, are sequential over all layers. A node is either of type "1" (original node), or "0" (positional dummy). The edges are always going from a lower to a higher layer.