Optimization Online


Exact Approaches to Multi-Level Vertical Orderings

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

Abstract: 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 to the latter, it can be formulated such that it does not merely consist of multiple sequentially linked bilevel quadratic ordering problems, but as a genuine multi-level problem with dense cost matrix. This allows us to describe the graphs' structures more compactly and therefore obtain solutions for graphs too large for MLCM in practice. In this paper we give a motivation and mathematical models for MLVO. We formulate linear and quadratic programs, including some strengthening constraint classes, and an SDP relaxation for MLVO.We compare all these approaches both theoretically and experimentally and show that MLVO's properties render linear and quadratic programming approaches inapplicable, even for small sparse graphs, while the SDP works surprisingly well in practice. This is in stark contrast to other ordering problems like MLCM, where such graphs are typically solved more efficiently with integer linear programs. Finally, we also compare our approach to related MLCM approaches.

Keywords: Quadratic ordering problem, ILP and SDP approaches, multi-layer graph drawings, crossing minimization

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

Category 2: Integer Programming ((Mixed) Integer Linear Programming )

Category 3: Integer Programming ((Mixed) Integer Nonlinear Programming )

Citation: Technical Report TR-FSUJ-CS-AE-11-02, v.1, Algorithm Engineering Group, Computer Science, FSU Jena, December 2011

Download: [PDF]

Entry Submitted: 06/06/2011
Entry Accepted: 06/06/2011
Entry Last Modified: 12/23/2011

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