Abstract

Title: Odd Crossing Number Is Not Crossing Number
Published: April 2005
Authors: Michael J. Pelsmajer, Marcus Schaefer, Daniel Štefankovic
Abstract: The crossing number of a graph is the minimum number of edge intersections in a plane drawing of a graph, where each intersection is counted separately. If instead we count the number of pairs of edges that intersect an odd number of times, we obtain the odd crossing number. We show that there is a graph for which these two concepts differ, answering a well-known open question on crossing numbers. To derive the result we study drawings of maps on the annulus.
Keywords: Crossing number, odd crossing number, pair crossing number
Full Paper: [postscript, pdf]