  Crossing Number is a celebrated problem in graph drawing. It is known to be
NP-complete since 1980s, and fairly involved techniques were already required
to show its fixed-parameter tractability when parameterized by the vertex cover
number. In this paper we prove that computing exactly the crossing number is
NP-hard even for graphs of path-width 12 (and as a result, even of tree-width
9). Thus, while tree-width and path-width have been very successful tools in
many graph algorithm scenarios, our result shows that general crossing number
computations unlikely (under P!=NP) could be successfully tackled using bounded
width of graph decompositions, which has been a 'tantalizing open problem' [S.
Cabello, Hardness of Approximation for Crossing Number, 2013] till now.
