Marcus Schaefer
School of Computer Science, Telecommunications & Information Systems
DePaul University

Crossing Numbers and Parameterized Complexity

The odd crossing number of a graph 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. Joint work with Michael Pelsmajer and Daniel Stefankovic


14, September, E1 Room 103, 3:00 pm

Last updated by jmillham AT iit DOT com on 9/12/07