[Discrete-math-seminar] Friday, Sept 14, 3pm

[Hemanshu Kaul]

Hello all,

We have our first talk of the semester scheduled for this Friday. The
room number is not fixed yet, it will be updated at the seminar website
before Friday: http://www.math.iit.edu/academics/sem_coll.html#RGsem . 


Date, Time, and Place: Friday, Sept 14, 3pm, E1 Bldg. Room ??, IIT.

Title: Crossing Numbers and Parameterized Complexity

Speaker: Marcus Schaefer, Depaul University

Abstract:

   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

See you all on Friday.

Hemanshu