Abstract

Title: Crossing Number of Graphs with Rotation Systems
Published: November 2005
Authors: Michael J. Pelsmajer, Marcus Schaefer, Daniel Štefankovic
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]