Michael Jünger, Eva K. Lee, Petra Mutzel, and Thomas Odenthal
May, 1997
In this paper, we study the multi-layered crossing number problem.
First, we present an integer programming formulation for the
crossing number problem on multi-layered graphs.
Polyhedral theory is then conducted on the
polytope associated with our formulation for the 2-layer crossing
number problem and several classes of facets are derived.
We then present a cutting plane algorithm for the 2-layer
crossing number problem based on the facets obtained. Numerical results
on computing the lower bounds for a set of instances are reported.
Key words: Crossing number, multi-layered graphs, polyhedral theory, cutting plane algorithm.