creators_name: Pach, János
creators_name: Tóth, Géza
editors_name: Healy, Patrick
editors_name: Nikolov, Nikola S.
editors_id: Healy, Patrick
editors_id: Nikolov, Nikola S.
type: confpaper
datestamp: 2006-02-22
lastmod: 2008-09-18 11:09:00
metadata_visibility: show
title: Crossing number of toroidal graphs
ispublished: pub
subjects: G.420
subjects: Z.1
full_text_status: none
abstract: 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.
    
date: 2006
date_type: published
publisher: Springer
pagerange: 334-342
refereed: FALSE
referencetext: G. Cairns and Y. Nikolayevsky.: Bounds for generalized thrackles, Discrete Comput. Geom., 23 (2000), 191--206.

B. Mohar and C. Thomassen.: Graphs on surfaces, Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore, MD, 2001.

G. Salazar and E. Ugalde: An improved bound for the crossing number of C\sb m\times C\sb n: a self-contained proof using mostly combinatorial arguments, Graphs Combin., 20 (2004), 247--253.
citation: Pach, János and Tóth, Géza (2006) Crossing number of toroidal graphs. [Conference Paper]