Title: Crossing Number of Graphs with Rotation Systems
Authors: Michael J. Pelsmajer, Marcus Schaefer, Daniel Štefankovič
Abstract: We show that computing the crossing number of a graph with a given rotation system is NP-complete. This result leads to a new and much simpler proof of Hlinĕnư's result, that computing the crossing number of a cubic graph (no rotation system) is NP-complete.
Full Paper:  [postscript, pdf]