## Crossing Number of Graphs with Rotation Systems
Pelsmajer, Michael J. and Schaefer, Marcus and Stefankovic, Daniel
(2008)
Full text not available from this repository. ## AbstractWe 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 Hlinvený's result, that computing the crossing number of a cubic graph (without rotation system) is NP-complete. We also investigate the special case of multigraphs with rotation systems on a fixed number $k$ of vertices. For k=1 and k=2 the crossing number can be computed in polynomial time and approximated to within a factor of 2 in linear time. For larger k we show how to approximate the crossing number to within a factor of k+4choose 4/5 in time O(m^k+2) on a graph with m edges.
Repository Staff Only: item control page References |