## Crossing Numbers and Parameterized Complexity
Pelsmajer, Michael J. and Schaefer, Marcus and Stefankovic, Daniel
(2008)
Full text not available from this repository. ## AbstractThe 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 that uses at most 9^k crossings, 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.
Repository Staff Only: item control page References |