Monotone Crossing Number

Pach, János and Tóth, Géza (2012) Monotone Crossing Number. In: Graph Drawing 19th International Symposium, GD 2011, September 21-23, 2011, Eindhoven, The Netherlands , pp. 278-289 (Official URL: http://dx.doi.org/10.1007/978-3-642-25878-7_27).

Full text not available from this repository.

Abstract

The monotone crossing number of G is defined as the smallest number of crossing points in a drawing of G in the plane, where every edge is represented by an x-monotone curve, that is, by a connected continuous arc with the property that every vertical line intersects it in at most one point. It is shown that this parameter can be strictly larger than the classical crossing number cr(G), but it is bounded from above by 2cr2 (G). This is in sharp contrast with the behavior of the rectilinear crossing number, which cannot be bounded from above by any function of cr(G).

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-25878-7_27
Classifications:G Algorithms and Complexity > G.420 Crossings
P Styles > P.480 Layered
ID Code:1262

Repository Staff Only: item control page

References

Bienstock, D., Dean, N.: Bounds for rectilinear crossing numbers. J. Graph Theory 17, 333–348 (1993)

Diestel, R.: Graph Theory, 3rd edn. Graduate Texts in Mathematics, vol. 173. Springer, Berlin (2005)

Erdős, P., Guy, R.K.: Crossing number problems, Amer. Math. Monthly 80, 52–58 (1973)

Fáry, I.: On straight line representation of planar graphs. Acta Univ. Szeged. Sect. Sci. Math. 11, 229–233 (1948)

Fulek, R., Pelsmajer, M.J., Schaefer, M., Štefankovič, D.: Hanani-Tutte, monotone drawings, and level-planarity (to appear)

Garey, M.R., Johnson, D.S.: Crossing number is NP-complete, SIAM J. Alg. Disc. Meth. 4, 312–316 (1983)

Garey, M.R., Johnson, D.S., Stockmeyer, L.J.: Some simplified NP-complete graph problems. Theoretical Computer Science 1, 237–267 (1976)

Guy, R.K.: The decline and fall of Zarankiewicz’s theorem. In: Guy, R.K. (ed.) Proof Techniques in Graph Theory, pp. 63–69. Academic Press, New York (1969)

Pach, J., Sterling, E.: Conways conjecture for monotone thrackles. Amer. Math. Monthly 118, 544–548 (2011)

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

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

Pach, J., Tóth, G.: Monotone drawings of planar graphs. J. Graph Theory 46, 39–47 (2004)

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

Pelsmajer, M.J., Schaefer, M., Štefankovič, D.: Removin independently even crossings. SIAM J. Discrete Math. 24, 379–393 (2010)

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

Tóth, G.: A better bound for the pair-crossing number (manuscript)

Turán, P.: A note of welcome. J. Graph Theory 1, 7–9 (1977)

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 Univ. Press, Cambridge (2005)

Woodall, D.R.: Thrackles and deadlock. In: Welsh, D.J.A. (ed.) Combinatorial Mathematics and Its Applications, pp. 335–348. Academic Press (1969)