Personal tools
You are here: Home Events Abstract Archives 2001 Computing crossing numbers in quadratic time

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.

Document Actions