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