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

research:mlvo

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:

- M. Chimani, P. Hungerländer.
**Multi-level Verticality Optimization: Concept, Strategies, and Drawing Scheme.**Technical Report TR-FSUJ-CS-AE-11-01. Algorithm Engineering Group, Computer Science, FSU Jena. June 2011.

- M. Chimani, P. Hungerländer.
**Exact Approaches to Multi-level Vertical Orderings.**Technical Report TR-FSUJ-CS-AE-11-02. Algorithm Engineering Group, Computer Science, FSU Jena. June 2011.

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.

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.

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.

research/mlvo.txt · Last modified: 2013/04/17 21:42 by chimani