Crossing Numbers of Graphs with Rotation Systems.

摘要

We show that computing the crossing number and the odd crossing number of a graph with a given rotation system is NP-complete. As a consequence we can show that many of the well-known crossing number notions are NP-complete even if restricted to cubic graphs (with or without rotation system). In particular, we can show that Tutte's independent odd crossing number is NP-complete, and we obtain a new and simpler proof of Hlineny's result that computing the crossing number of a cubic graph is NP-complete. We also consider the special case of multigraphs with rotation systems on a fixed number k of vertices. For k = 1 we give an O(mlogm) algorithm, where m is the number of edges, and for loopless multigraphs on 2 vertices we present a linear time 2-approximation algorithm. In both cases there are interesting connections to edit-distance problems on (cyclic) strings. For larger k we show how to approximate the crossing number to within a factor of (k+4 4/5) in time O(mk log m) on a graph with m edges.