|Abstrakt:||The Crossing Number Problem is the problem to decide, for a given integer k > 0, whether a graph G can be embedded in the plane with k or fewer pairwise edge crossings.
In this thesis, we survey and analyse exact, approximate, and heuristic algorithms for computing the crossing number of a graph, and some of its variants. Since the Crossing Number Problem is NP-complete, no exact polynomial algorithms are known for the general problem. However, algorithms based on a branch-and-cut approach have been reported to solve medium sized instances to provable optimality.
For graphs of bounded degree, approximate algorithms based on a bisection width concept have been developed.
In practice, the problem is mostly attacked heuristically using a planarizalion approach consisting of two NP-hard steps, i.e., the Maximum Planar Subgraph Problem and the Constrained Crossing Minimization Problem.
We also propose two new heuristics for the (fixed) linear crossing number, respectively, based on the Simulated Annealing scheme and compare their performance with the heuristics known from literature.