185 KB9 KB197720262006Mohar, Bojanštevilka:3letnik:30str. 301-303ISSN:0350-5596COBISSID:20379431URN:URN:NBN:SI:doc-VLFA6YN7enSlovensko društvo InformatikaInformatica (Ljubljana)matematikamathematicsravninski grafiRiskinova tezateorija grafovOn the crossing number of almost planar graphs|If ?$G$? is a plane graph and ?$x,y \in V(G)$?, then the dual distance of ?$x$? and ?$y$? is equal to the maximum number of crossings of ?$G$? with a curve in the plane joining ?$x$? and ?$y$?. Riskin proved that if ?$G_0$? is a 3-connected cubic planar graph, and ?$x, y$? are its vertices at dual distance ?$d$?, then the crossing number of the graph ?$G_0 + xy$? is equal to ?$d$?. Riskin asked if his results holds for arbitrary 3-connected planar graphs. We show that this is not the case (not even for every 5-connected planar graph ?$G_0$?)Če je ?$G$? grad, vložen v ravnini, in sta ?$x$? in ?$y$? in njegovi vozlišči, definiramo ?$d(x,y)$? kot minimalno število točk na ?$G$?, ki jih sekajo krivulje od ?$x$? do ?$y$?. Riskin je dokazal, da je v primeru ravninskega 3-povezanega kubičnega grafa ?$G_0$? število ?$d(x,y)$? enako prekrižnemu številu grafa ?$G_0+xy$?. Vprašal je, če enako velja tudi v primeru, ko ?$G_0$? ni kubičen graf. V delu je dokazano, da to ni res, tudi če dodatno privzamemo, da je ?$G_0$? 5-povezanTEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaSlovensko društvo Informatika