Das Kreuzungszahlproblem wird von Graphentheoretikern seit über 60 Jahren betrachtet, jedoch ist noch immer sehr wenig über dieses einfache und zugleich hochkomplizierte Ma der Nichtplanarität bekannt. Die Aufgabenstellung ist simpel: Gegeben ein Graph, zeichnen Sie ihn mit der kleinstmöglichen Anzahl an Kantenkreuzungen. Nicht nur Graphentheoretiker sondern auch Informatiker beschäftigten sich ausgiebig mit dieser Aufgabe, denn es handelt sich dabei um ein zentrales Konzept im Chipdesign und im automatischen Graphenzeichnen. Zwar existieren Algorithmen um das Problem heuristisch zu lösen, jedoch wissen wir, dass es im Allgemeinen NP-vollständig ist. Darüberhinaus ist auch unbekannt, ob sich das Problem, außer in Spezialfällen, effizient approximieren lässt. In dieser Dissertation, versuchen wir das Problem mit Hilfe der Mathematischen Programmierung zu lösen. Wir zeigen, wie man das Kreuzungszahlproblem als verschiedene Systeme von linearen Ungleichungen formulieren kann und diskutieren wie man diese Formulierungen für nicht allzu große Graphen beweisbar optimal und in akzeptabler Zeit lösen kann - unabhängig von seiner formalen Komplexitätsklasse. Wir stellen dazu benötigte maßgeschneiderte Branch-and-Cut-and-Price Techniken vor, und präsentieren einen effizienten Algorithmus zur Vorverarbeitung; dieser ist auch für andere traditionelle Ma e der Nichtplanarität geeignet. Wir diskutieren Erweiterungen unserer Ideen für verwandte Kreuzungszahlkonzepte die in der Praxis auftreten, und zeigen eine praktische Anwendung eines vormals rein theoretisch behandelten Kreuzungszahl-Derivats auf. Diese Arbeit enthält auch eine ausführliche experimentelle Studie der präsentierten Formulierungen und Algorithmen, sowie einen Ausblick über deren mögliche Nutzung für graphentheoretische Fragen bezüglich der Kreuzungszahlen von speziellen Graphenklassen.

The graph theoretic problem of crossing numbers has been around for over 60 years, but still very little is known about this simple, yet intricate nonplanarity measure. The question is easy to state: Given a graph, draw it in the plane with the minimum number of edge crossings. A lot of research has been devoted to giving an answer to this question, not only by graph theoreticians, but also by computer scientists. The crossing number is central to areas like chip design and automatic graph drawing. While there are algorithms to solve the problem heuristically, we know that it is in general NP-complete. Furthermore, we do not know if the problem is efficiently approximable, except for some special cases. In this thesis, we tackle the problem using Mathematical Programming. We show how to formulate the crossing number problem as systems of linear inequalities, and discuss how to solve these formulations for reasonably sized graphs to provable optimality in acceptable time--despite its theoretical complexity class. We present non-standard branch-and-cut-and-price techniques to achieve this goal, and introduce an efficient preprocessing algorithm, also valid for other traditional non-planarity measures. We discuss extensions of these ideas to related crossing number variants arising in practice, and show a practical application of a formerly purely theoretic crossing number derivative. The thesis also contains an extensive experimental study of the formulations and algorithms presented herein, and an outlook on its applicability for graph theoretic questions regarding the crossing numbers of special graph classes.