Odd Crossing Number Is Not Crossing Number

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

Full text not available from this repository.

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 {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
ID Code:720

Repository Staff Only: item control page

References

Dan Archdeacon. Problems in topological graph theory. http://www.emba.uvm.edu/~archdeac/problems/altcross.html (accessed April 7th, 2005).

Michael R. Garey and David S. Johnson. Crossing number is NP-complete. SIAM Journal on Algebraic and Discrete Methods, 4(3):312-316, 1983.

Jonathan L. Gross and Thomas W. Tucker. Topological graph theory. Dover Publications Inc., Mineola, NY, 2001. Reprint of the 1987 original.

Chaim Chojnacki (Haim Hanani). Über wesentlich unplättbare Kurven im drei-dimensionalen Raume. Fundamenta Mathematicae, 23:135-142, 1934.

Petr Kolman and Jiri Matousek. Crossing number, pair-crossing number, and expansion. J. Combin. Theory Ser. B, 92(1):99-113, 2004.

János Pach. Crossing numbers. In Discrete and computational geometry (Tokyo, 1998), volume 1763 of Lecture Notes in Comput. Sci., pages 267-273. Springer, Berlin, 2000.

János Pach and Géza Tóth. Which crossing number is it anyway? J. Combin. Theory Ser. B, 80(2):225-246, 2000.

Michael J. Pelsmajer, Marcus Schaefer and Daniel Stefankovic. Removing even crossings. Manuscript, April 2005.

László A. Székely. A successful concept for measuring non-planarity of graphs: the crossing number. Discrete Math., 276(1-3):331-352, 2004. 6th International Conference on Graph Theory.

W. T. Tutte. Towards a theory of crossing numbers. J. Combinatorial Theory, 8:45-53, 1970.

Pavel Valtr. On the pair-crossing number. Manuscript.

Douglas West. Open problems - graph theory and combinatorics. http://www.math.uiuc.edu/~west/openp/ (accessed April 7th, 2005).