title: Crossing number of toroidal graphs
creator: Pach, János
creator: Tóth, Géza
subject: G.420 Crossings
subject: Z.001 General
description: It is shown that if a graph of n vertices can be drawn on the torus without edge crossings and the maximum degree of its vertices is at most d, then its planar crossing number cannot exceed c_dn, where c_d is a constant depending only on d. This bound, conjectured by Brass, cannot be improved, apart from the value of the constant. We strengthen and generalize this result to the case when the graph has a crossing-free drawing on an orientable surface of higher genus and there is no restriction on the degrees of the vertices.      
publisher: Springer
contributor: Healy, Patrick
contributor: Nikolov, Nikola S.
date: 2006
type: Conference Paper
type: NonPeerReviewed
identifier: Pach, János and Tóth, Géza (2006) Crossing number of toroidal graphs. [Conference Paper]
relation: http://gdea.informatik.uni-koeln.de/702/