Crossing Numbers of Graphs with Rotation Systems

Crossing Numbers of Graphs with Rotation Systems

0.00 Avg rating0 Votes
Article ID: iaor20114252
Volume: 60
Issue: 3
Start Page Number: 679
End Page Number: 702
Publication Date: Jul 2011
Journal: Algorithmica
Authors: , ,
Keywords: NP-complete
Abstract:

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 Hliněný’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(mlog m) 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 choose 4 / 5 equ1 in time O(m k log m) on a graph with m edges.

Reviews

Required fields are marked *. Your email address will not be published.