# The Complexity of Computing the Cylindrical and the $t$-Circle Crossing Number of a Graph

### Abstract

A plane drawing of a graph is *cylindrical* if there exist two concentric circles that contain all the vertices of the graph, and no edge intersects (other than at its endpoints) any of these circles. The *cylindrical crossing number* of a graph \(G\) is the minimum number of crossings in a cylindrical drawing of \(G\). In his influential survey on the variants of the definition of the crossing number of a graph, Schaefer lists the complexity of computing the cylindrical crossing number of a graph as an open question. In this paper, we prove that the problem of deciding whether a given graph admits a cylindrical embedding is NP-complete, and as a consequence we show that the \(t\)-cylindrical crossing number problem is also NP-complete. Moreover, we show an analogous result for the natural generalization of the cylindrical crossing number, namely the \(t\)-*crossing number*.