Title: |
Crossing Numbers and
Parameterized Complexity |

Authors: |
Michael J. Pelsmajer, Marcus Schaefer, Daniel Štefankovič |

Abstract: |
The odd crossing
number of G is the smallest number of pairs of edges that cross
an odd number of times in any drawing of G. We show that there
always is a drawing realizing the odd crossing number of G whose
crossing number is at most 9^{k+1}, where k is the
odd crossing number of G. As a consequence of this and a result
of Grohe we can show that the odd crossing number is fixed-parameter
tractable. |

Full Paper: |
[postscript, pdf] |