Computing crossing number in linear time

We show that for every fixed k , there is a linear time algorithm that decides whether or not 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. This answers the question posed by Grohe (STOC'01 and JCSS 2004). Our algorithm can be viewed as a generalization of the seminal result by Hopcroft and Tarjan lin1, which determines if a given graph is planar in linear time.

Authors

• Ken-ichi Kawarabayashi
• Bruce A. Reed

Keywords

• tree-width
• crossing number
• linear time algorithm