Crossing Number of Graphs with Rotation SystemsPelsmajer, Michael J. and Schaefer, Marcus and Štefankovič, Daniel (2008) Crossing Number of Graphs with Rotation Systems. In: Graph Drawing 15th International Symposium, GD 2007, September 2426, 2007 , pp. 312(Official URL: http://dx.doi.org/10.1007/9783540775379_3). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783540775379_3
AbstractWe show that computing the crossing number of a graph with a given rotation system is NPcomplete. 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 NPcomplete. 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.
Actions (login required)
