
2
Crossings and Planariz at ion
Christoph Buchheim
TU Dortmund
Markus Chimani
Friedrich-Schiller-Universit¨at
Jena
Carsten Gutwenger
TU Dortmund
Michael J¨unger
University of Cologne
Petra Mutzel
TU Dortmund
2.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.2 Crossing Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
Known Bounds
2.3 Complexity of Crossing Minimizat i on . . . . . . . . . . . . . . . . . . . 50
NP-hardness
•
Fixed Parameter Tractability
2.4 Exact Crossing Minimizat i on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
Sub ...