4pm Tuesday 16 October 2001
Room 2511, JCMB, King's Buildings
Abstract
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.
Martin Grohe
Tuesday 9 October 2001
An error occured whilst processing this directive