Computing crossing numbers in quadratic time

We show that for every fixed k\ge 0 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.

Authors

• Martin Grohe

Keywords

No keywords are indexed for this paper.