Abstract: The crossing number of a graph is the minimum number of edge crossings needed in a drawing of the graph into 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 into the plane with at most k crossings.
September 14, 2001 - Martin Grohe