Markus Chimani

Exact Approaches to Multi-Level Vertical Orderings

  • Markus Chimani
  • Philipp Hungerländer
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming, Semi-definite Programming Tags , , ,

    We present a semide nite programming (SDP) approach for the problem of ordering vertices of a layered graph such that the edges of the graph are drawn as vertical as possible. This Multi-Level Vertical Ordering (MLVO) problem is a quadratic ordering problem and conceptually related to the well-studied problem of Multi-Level Crossing Minimization (MLCM). In contrast … Read more

    Multi-level Verticality Optimization: Concept, Strategies, and Drawing Scheme

  • Markus Chimani
  • Philipp Hungerländer
    • Categories Applications - Science and Engineering, Semi-definite Programming Tags , , ,

    In traditional multi-level graph drawing – known as Sugiyama’s framework – the number of crossings is considered one of the most important goals. Herein, we propose the alternative concept of optimizing the verticality of the drawn edges. We formally specify the problem, discuss its relative merits, and show that drawings that are good w.r.t. verticality … Read more