Drawings of graphs on surfaces with few crossings |
| |
Authors: | F Shahrokhi L A Székely O Sýkora I Vrt'o |
| |
Affiliation: | (1) Department of Computer Science, University of North Texas, P.O. Box 13886, 76203 Denton, TX, USA;(2) Department of Computer Science, Eötvös University, Múzeurn krt. 6-8, 1088 Budapest, Hungary;(3) Institute for Informatics, Slovak Academy of Sciences, Dúbravská 9, P.O. Box 56, 840 00 Bratislava 4, Slovakia |
| |
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.The research of the third and the fourth authors was partially supported by Grant No. 2/1138/94 of the Slovak Academy of Sciences and by EC Cooperative action IC1000 Algorithms for Future Technologies (Project ALTEC). A preliminary version of this paper was presented at WG93 and published in Lecture Notes in Computer Science, Vol. 790, 1993, pp. 388–396. |
| |
Keywords: | Crossing number Orientable and nonorientable surface Topological graph theory |
本文献已被 SpringerLink 等数据库收录! |
|