Odd Crossing Number Is Not Crossing Number

Pelsmajer, Michael J. and Schaefer, Marcus and Štefankovič, Daniel (2006) Odd Crossing Number Is Not Crossing Number. In: Graph Drawing 13th International Symposium, GD 2005, September 12-14, 2005 , pp. 386-396(Official URL: http://dx.doi.org/10.1007/11618058_35).

Full text not available from this repository.


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 {em 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 (graphs with rotation systems).

Item Type: Conference Paper
Additional Information: 10.1007/11618058_35
Classifications: G Algorithms and Complexity > G.420 Crossings
Z Theory > Z.001 General
URI: http://gdea.informatik.uni-koeln.de/id/eprint/720

Actions (login required)

View Item View Item