caa a22 4500 445804386 CHVBK 20180317145152.0 cr unu---uuuuu 170323e20110701xx s 000 0 eng 10.1007/s00453-009-9343-y doi (NATIONALLICENCE)springer-10.1007/s00453-009-9343-y Crossing Numbers of Graphs with Rotation Systems [Elektronische Daten] [Michael Pelsmajer, Marcus Schaefer, Daniel Štefankovič] 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\choose4}/5$ in time O(m klog m) on a graph with m edges. Springer Science+Business Media, LLC, 2009 Crossing number nationallicence Rotation system nationallicence Odd crossing number nationallicence Independent odd crossing number nationallicence Tournaments nationallicence NP-completeness nationallicence Pelsmajer Michael Department of Applied Mathematics, Illinois Institute of Technology, 60616, Chicago, IL, USA aut Schaefer Marcus Department of Computer Science, DePaul University, 60604, Chicago, IL, USA aut Štefankovič Daniel Computer Science Department, University of Rochester, 14627-0226, Rochester, NY, USA aut Algorithmica Springer-Verlag 60/3(2011-07-01), 679-702 0178-4617 60:3<679 2011 60 453 https://doi.org/10.1007/s00453-009-9343-y text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-009-9343-y text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Pelsmajer Michael Department of Applied Mathematics, Illinois Institute of Technology, 60616, Chicago, IL, USA aut NATIONALLICENCE 700 1- Schaefer Marcus Department of Computer Science, DePaul University, 60604, Chicago, IL, USA aut NATIONALLICENCE 700 1- Štefankovič Daniel Computer Science Department, University of Rochester, 14627-0226, Rochester, NY, USA aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 60/3(2011-07-01), 679-702 0178-4617 60:3<679 2011 60 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer