ISSN:
1432-0541
Keywords:
Crossing number
;
Orientable and nonorientable surface
;
Topological graph theory
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract We give drawings of a complete graphK n withO(n 4 log2 g/g) many crossings on an orientable or nonorientable surface of genusg ≥ 2. We use these drawings ofK n and give a polynomial-time algorithm for drawing any graph withn vertices andm edges withO(m 2 log2 g/g) many crossings on an orientable or nonorientable surface of genusg ≥ 2. Moreover, we derive lower bounds on the crossing number of any graph on a surface of genusg ≥ 0. The number of crossings in the drawings produced by our algorithm are within a multiplicative factor ofO(log2 g) from the lower bound (and hence from the optimal) for any graph withm ≥ 8n andn 2/m ≤g ≤m/64.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02086611
