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 , pp. 3-12(Official URL: http://dx.doi.org/10.1007/978-3-540-77537-9_3).

Full text not available from this repository.

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 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.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-540-77537-9_3
Classifications: G Algorithms and Complexity > G.420 Crossings
URI: http://gdea.informatik.uni-koeln.de/id/eprint/823

Actions (login required)

View Item View Item