Optimization Online


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

Markus Chimani (markus.chimani***at***uni-jena.de)
Philipp Hungerländer (philipp.hungerlaender***at***uni-klu.ac.at)

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.

Keywords: Multi-layer graph drawings, crossing minimization, Sugiyama's framework, exact and heuristic approaches

Category 1: Applications -- Science and Engineering

Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Citation: Technical Report TR-FSUJ-CS-AE-11-01, v.2, Algorithm Engineering Group, Computer Science, FSU Jena, April 2012

Download: [PDF]

Entry Submitted: 06/06/2011
Entry Accepted: 06/06/2011
Entry Last Modified: 04/17/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society