Accession Number

PB2013102709

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 NPcomplete. As a consequence we can show that many of the wellknown crossing number notions are NPcomplete even if restricted to cubic graphs (with or without rotation system). In particular, we can show that Tutte's independent odd crossing number is NPcomplete, and we obtain a new and simpler proof of Hlineny's result that computing the crossing number of a cubic graph is NPcomplete. 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 2approximation algorithm. In both cases there are interesting connections to editdistance 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
