On the Crossing Number of Almost Planar Graphs
Bojan Mohar · 2006
If G is a plane graph and x, y ∈ V (G), then the dual distance of x and y is equal to the minimum number of crossings of G with a closed curve in the plane joining x and y. Riskin [7] proved that if G0 is a 3connected cubic planar graph, and x, y are its vertices at dual distance d, then the crossing number of the graph G0 + xy is equal to d. Riskin asked if his result holds for arbitrary 3-connected planar graphs. In this paper it is proved that this is not the case (not even for every 5-connected planar graph G0). Povzetek: Analizirana je Riskinova teza o planarnih grafih. 1