  


Exact Approaches to MultiLevel Vertical Orderings
Markus Chimani (markus.chimaniunijena.de) Abstract: We present a semidenite 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 MultiLevel Vertical Ordering (MLVO) problem is a quadratic ordering problem and conceptually related to the wellstudied problem of MultiLevel 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 multilevel 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, multilayer graph drawings, crossing minimization Category 1: Linear, Cone and Semidefinite Programming (Semidefinite Programming ) Category 2: Integer Programming ((Mixed) Integer Linear Programming ) Category 3: Integer Programming ((Mixed) Integer Nonlinear Programming ) Citation: Technical Report TRFSUJCSAE1102, v.1, Algorithm Engineering Group, Computer Science, FSU Jena, December 2011 Download: [PDF] Entry Submitted: 06/06/2011 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  