Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: The crossing number of a projective graph is quadratic in the face–width. | The crossing number of a projective graph is quadratic in the face-width I. Gitler Departamento de Matemáticas CINVESTAV Mexico DF Mexico P. Hlinenyy Faculty of Informatics Masaryk University Botanicka 68a 602 00 Brno Czech Republic J. Leanos G. Salazar z Instituto de Fásica UASLP San Luis Potosá SLP Mexico Submitted Jul 18 2007 Accepted Feb 26 2008 Published Mar 20 2008 Mathematics Subject Classification 05C10 05C62 05C85 Abstract We show that for each integer g 0 there is a constant cg 0 such that every graph that embeds in the projective plane with sufficiently large face-width r has crossing number at least cgr2 in the orientable surface Eg of genus g. As a corollary we give a polynomial time constant factor approximation algorithm for the crossing number of projective graphs with bounded degree. 1 Introduction We recall that the face-width of a graph G embedded in a surface s is the minimum number of intersections of G with a noncontractible curve in s. Fiedler et al. 7 proved that the orientable genus of a projective graph grows linearly with the face-width. Our aim is to show that for each integer g 0 the crossing number crg of projective graphs in the closed orientable surface sg of genus g grows quadratically with the face-width. igitler@ yhlineny@. Supported partly by grant GACR 201 08 0308. z jelema gsalazar @. Supported by CONACYT grant 45903 and FAI-UASLP. THE ELECTRONIC JOURNAL OF COMBINATORICS 15 2008 R46 1 Theorem For every integer g 0 there are constants cg Tg 0 such that if G embeds in the projective plane with face-width at least r rg then the crossing number crg G of G in vg is at least cgr2. We remark that cr0 the crossing number in the sphere coincides with the usual crossing number in the plane. Our strategy for proving Theorem is to show the existence of sufficiently large grid-like structures so called diamond grids Theorem in projective graphs and then prove that diamond grids have .
