# Computing crossing numbers in quadratic time

Martin Grohe LFCS 4pm Tuesday 16 October 2001 Room 2511, JCMB, King's Buildings

The crossing number of a graph is the least number of edge crossings needed to draw the graph in the plane. We show that for every fixed k there is a quadratic time algorithm that decides whether a given graph has crossing number at most k and, if this is the case, computes a drawing of the graph in the plane with at most k crossings.