Documents in the NTIS Technical Reports collection are the results of federally funded research. They are directly submitted to or collected by NTIS from Federal agencies for permanent accessibility to industry, academia and the public.  Before purchasing from NTIS, you may want to check for free access from (1) the issuing organization's website; (2) the U.S. Government Printing Office's Federal Digital System website http://www.gpo.gov/fdsys; (3) the federal government Internet portal USA.gov; or (4) a web search conducted using a commercial search engine such as http://www.google.com.
Accession Number PB2013-102709
Title Crossing Numbers of Graphs with Rotation Systems.
Publication Date Jul 2009
Media Count 30p
Personal Author D. Stefankovic M. Schaefer M. J. Pelsmajer
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 Hlineny'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(mlogm) 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 4/5) in time O(mk log m) on a graph with m edges.
Keywords Algorithms
Crossings
Graphs
Rotation
String models
Theorems
Vertices


 
Source Agency Single Entry
NTIS Subject Category 72B - Algebra, Analysis, Geometry, & Mathematical Logic
Corporate Author Rochester Univ., NY. Dept. of Computer Science.
Document Type Technical report
Title Note N/A
NTIS Issue Number 1305
Contract Number N/A

Science and Technology Highlights

See a sampling of the latest scientific, technical and engineering information from NTIS in the NTIS Technical Reports Newsletter

Acrobat Reader Mobile    Acrobat Reader