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

Authors

  • Markus Chimani
  • Philipp Hungerländer

DOI:

https://doi.org/10.7155/jgaa.00296

Keywords:

graph drawing , multi-layer drawings , Sugiyama , semi-definite programming , heuristics , non-proper graphs , crossing minimization

Abstract

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 in fact also have a low number of crossings. We present heuristic and exact approaches to tackle the verticality problem and study them in practice. Furthermore, we present a new drawing scheme (inherently bundling edges and drawing them monotonously), especially suitable for verticality optimization. It works without the traditional subdivision of edges, i.e., edges may span multiple levels, and therefore potentially allows to tackle larger graphs.

Downloads

Download data is not yet available.

Downloads

Published

2013-03-01

How to Cite

Chimani, M., & Hungerländer, P. (2013). Multi-level Verticality Optimization: Concept, Strategies, and Drawing Scheme. Journal of Graph Algorithms and Applications, 17(3), 329–362. https://doi.org/10.7155/jgaa.00296

Issue

Section

Articles

Categories