Crossing Numbers and Parameterized Complexity

Pelsmajer, Michael J. and Schaefer, Marcus and Štefankovič, Daniel (2008) Crossing Numbers and Parameterized Complexity. In: Graph Drawing 15th International Symposium, GD 2007, September 24-26, 2007 , pp. 31-36(Official URL:

Full text not available from this repository.


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 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.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-540-77537-9_6
Classifications: G Algorithms and Complexity > G.420 Crossings

Actions (login required)

View Item View Item