|
|
 |
|
|
Exact Crossing Minimization
|
| Begin: |
January 2004 |
|
| End: |
open |
|
| Status: |
ongoing |
|
|
|
|
|
Description: |
> |
The crossing number of a graph is the minimum number of edge crossings
in any drawing of the graph in the plane. Extensive research has
produced bounds on the crossing number and exact formulae for special
graph classes, yet the crossing numbers of graphs such as K_11 or
K_9,11 are still unknown. Finding the crossing number is NP-hard
for general graphs and no practical algorithm for its computation has
been published so far. In our project, we developed an integer linear
programming formulation that is based on a reduction of the general
problem to a restricted version of the crossing number problem in
which each edge may be crossed at most once. We also developed cutting
plane generation heuristics and a column generation scheme. As we
demonstrated in a computational study, a branch-and-cut algorithm based
on these techniques as well as recently published preprocessing
algorithms can be used to successfully compute the crossing number for
small to medium sized general graphs. |
|
|
|
|
|
|
| People involved: |
> |
,
(Universität Dortmund),
Dietmar Ebner (TU Wien),
(Universität Dortmund),
,
(Freie Universität Berlin),
(Universität Dortmund),
(CSIRO Melbourne)
|
|
| |
|
|
|
|
Funding:
|
> |
European Commission (RTN ADONET 504438)
|
|
|
|
|
|
|
|
Documents:
|
> |
| |
|
|
|
|
|
|
|
|
|
