A Polyhedral Approach to the Multi-Layer Crossing Minimization Problem (Extended Abstract)

Jünger, Michael and Lee, Eva K. and Mutzel, Petra and Odenthal, Thomas (1998) A Polyhedral Approach to the Multi-Layer Crossing Minimization Problem (Extended Abstract). In: Graph Drawing 5th International Symposium, GD '97, September 18-20, 1997 , pp. 13-24(Official URL: http://dx.doi.org/10.1007/3-540-63938-1_46).

Full text not available from this repository.

Abstract

We study the multi-layer crossing minimization problem from a polyhedral point of view. After the introduction of an integer programming formulation of the multi-layer crossing minimization problem, we examine the 2-layer case and derive several classes of facets of the associated polytope. Preliminary computational results for 2- and 3-layer instances indicate, that the usage of the corresponding facet-defining inequalities in a branch-and-cut approach may only lead to a practically useful algorithm, if deeper polyhedral studies are conducted.

Item Type: Conference Paper
Additional Information: 10.1007/3-540-63938-1_46
Classifications: G Algorithms and Complexity > G.700 Layering
G Algorithms and Complexity > G.420 Crossings
URI: http://gdea.informatik.uni-koeln.de/id/eprint/69

Actions (login required)

View Item View Item