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$?).

Rights

URN

URN:NBN:SI:DOC-VLFA6YN7

COBISSID

20379431

Added

21.04.2016

Metadata

Citation

APA:

Mohar, Bojan (2006). On the crossing number of almost planar graphs. Informatica (Ljubljana), volume 30, issue 3, str. 301-303. URN:NBN:SI:DOC-VLFA6YN7 from http://www.dlib.si

MLA:

Mohar, Bojan. "On the crossing number of almost planar graphs." Informatica (Ljubljana) volume 30. issue 3 (2006) str. 301-303.
<http://www.dlib.si/?URN=URN:NBN:SI:DOC-VLFA6YN7>

Informatica
1977-
(Assembly record)