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 graphKn withO(n4 log2g/g) many crossings on an orientable or nonorientable surface of genusg 2. We use these drawings ofKn and give a polynomial-time algorithm for drawing any graph withn vertices andm edges withO(m2 log2g/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(log2g) from the lower bound (and hence from the optimal) for any graph withm 8n andn2/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 等数据库收录! |
|