The complexity of computing the cylindrical and the tcircle crossing number of a graph
Article

 Overview

 Identity

 Additional Document Info

 View All

Overview
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 NPcomplete, and as a consequence we show that the tcylindrical crossing number problem is also NPcomplete. Moreover, we show an analogous result for the natural generalization of the cylindrical crossing number, namely the tcircle crossing number. © The author. Released under the CC BY license (International 4.0).
publication date
funding provided via
published in
Identity
Digital Object Identifier (DOI)
Additional Document Info
start page
end page
volume
issue