Crossing Number of Graphs with Rotation Systems
Pelsmajer, Michael J. and Schaefer, Marcus and Stefankovic, Daniel (2008) Crossing Number of Graphs with Rotation Systems. In: Graph Drawing 15th International Symposium, GD 2007, September 24-26, 2007, Sydney, Australia , pp. 3-12 (Official URL: http://dx.doi.org/10.1007/978-3-540-77537-9_3).
Full text not available from this repository.
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 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