Removing Independently Even Crossings

Pelsmajer, Michael J. and Schaefer, Marcus and Stefankovic, Daniel (2010) Removing Independently Even Crossings. In: Graph Drawing 17th International Symposium, GD 2009, September 22-25, 2009, Chicago, IL, USA , pp. 201-206 (Official URL: http://dx.doi.org/10.1007/978-3-642-11805-0_20).

Full text not available from this repository.

Abstract

We show that cr(G) ≤ 2 iocr(G) settling an open problem of Pach and Tóth [5,1]. Moreover, iocr(G) = cr(G) if iocr(G) ≤ 2.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-11805-0_20
Classifications:G Algorithms and Complexity > G.420 Crossings
ID Code:1098

Repository Staff Only: item control page

References

Brass, P., Moser, W., Pach, J.: Research Problems in Discrete Geometry. Springer, New York (2005)

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

Norine, S.: Pfaffian graphs, T -joins and crossing numbers. Combinatorica 28(1), 89–98 (2008)

Pach, J., Sharir, M.: Combinatorial geometry and its algorithmic applications: The Alcalá lectures. Mathematical Surveys and Monographs, vol. 152. American Mathematical Society, Providence (2009)

Pach, J., T´th, G.: Thirteen problems on crossing numbers. Geombinatorics 9(4), o 194–207 (2000)

Pach, J., T´th, G.: Which crossing number is it anyway? J. Combin. Theory Ser. o B 80(2), 225–246 (2000)

Pelsmajer, M.J., Schaefer, M., Stasi, D.: Strong Hanani–Tutte on the projective plane. SIAM Journal on Discrete Mathematics 23(3), 1317–1323 (2009)

Pelsmajer, M.J., Schaefer, M., Stefankovic, D.: Removing even crossings. J. Combin. Theory Ser. B 97(4), 489–500 (2007)

Pelsmajer, M.J., Schaefer, M., Stefankovic, D.: Crossing number of graphs with rotation systems. In: Hong, S.-H., Nishizeki, T., Quan, W. (eds.) GD 2007. LNCS, vol. 4875, pp. 3–12. Springer, Heidelberg (2008)

Pelsmajer, M.J., Schaefer, M., Stefankovic, D.: Removing even crossings on surfaces. European Journal of Combinatorics 30(7), 1704–1717 (2009)

Pelsmajer, M.J., Schaefer, M., Stefankovic, D.: Crossing numbers and parameterized complexity. In: Hong, S.-H., Nishizeki, T., Quan, W. (eds.) GD 2007. LNCS, vol. 4875, pp. 31–36. Springer, Heidelberg (2008)

Pelsmajer, M.J., Schaefer, M., Stefankovic, D.: Odd crossing number and crossing number are not the same. Discrete Comput. Geom. 39(1), 442–454 (2008)

Székely, L.A.: A successful concept for measuring non-planarity of graphs: the crossing number. Discrete Math. 276(1-3), 331–352 (2004)

Székely, L.A.: An optimality criterion for the crossing number. Ars Math. Cone temp. 1(1), 32–37 (2008)

Tao, T., Vu, V.: Additive combinatorics. Cambridge Studies in Advanced Mathematics, vol. 105. Cambridge University Press, Cambridge (2006)

Tóth, G.: Note on the pair-crossing number and the odd-crossing number. Discrete Comput. Geom. 39(4), 791–799 (2008)

Tutte, W.T.: Toward a theory of crossing numbers. J. Combinatorial Theory 8, 45–53 (1970)

Valtr, P.: On the pair-crossing number. In: Combinatorial and Computational Geometry. Math. Sci. Res. Inst. Publ., vol. 52, pp. 569–575. Cambridge University Press, Cambridge (2005)

van der Holst, H.: Algebraic characterizations of outerplanar and planar graphs. European J. Combin. 28(8), 2156–2166 (2007)