Adjacent Crossings Do Matter

Radoslav, Fulek and Pelsmajer, Michael J. and Schaefer, Marcus and Štefankovič, Daniel (2012) Adjacent Crossings Do Matter. In: Graph Drawing 19th International Symposium, GD 2011, September 21-23, 2011, Eindhoven, The Netherlands , pp. 343-354 (Official URL: http://dx.doi.org/10.1007/978-3-642-25878-7_33).

Full text not available from this repository.

Abstract

In a drawing of a graph, two edges form an odd pair if they cross each other an odd number of times. A pair of edges is independent if they share no endpoint. For a graph G, let ocr(G) be the smallest number of odd pairs in a drawing of G and let iocr(G) be the smallest number of independent odd pairs in a drawing of G. We construct a graph G with iocr(G) < ocr(G), answering a question by Székely, and—for the first time—giving evidence that crossings of adjacent edges may not always be trivial to eliminate. The graph G is based on a separation of iocr and ocr for monotone drawings of ordered graphs. A drawing of a graph is x-monotone if every edge intersects every vertical line at most once and every vertical line contains at most one vertex. A graph is ordered if each of its vertices is assigned a distinct x-coordinate. We construct a family of ordered graphs such that for x-monotone drawings, the monotone variants of ocr and iocr satisfy mon-iocr(G) < O(mon-ocr(G)1/2 ).

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-25878-7_33
Classifications:G Algorithms and Complexity > G.420 Crossings
ID Code:1268

Repository Staff Only: item control page

References

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

Fulek, R., Pelsmajer, M.J., Schaefer, M., Štefankovič, D.: Hanani-Tutte, monotone drawings, and level-planarity. Accepted for WG (2011)

Chojnacki, C., Hanani, H.: Uber wesentlich unpl ̈ttbare Kurven im dreidimensionalen Raume. Fundamenta Mathematicae 23, 135–142 (1934)

Kainen, P.C.: A lower bound for crossing numbers of graphs with applications to Kn , Kp, q , and Q(d). J. Combinatorial Theory Ser. B 12, 287–298 (1972)

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

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

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

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., Štefankovič, D.: Removing even crossings. J. Combin. Theory Ser. B 97(4), 489–500 (2007)

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

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

Pelsmajer, M.J., Schaefer, M., Štefankovič, D.: Removing independently even crossings. SIAM Journal on Discrete Mathematics 24(2), 379–393 (2010)

Pelsmajer, M.J., Schaefer, M., Štefankovič, D.: Crossing numbers of graphs with rotation systems. Algorithmica 60, 679–702 (2011), doi:10.1007/s00453-009-9343-y

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.: Progress on Crossing Number Problems. In: Vojtáš, P., Bieliková M.,Charron-Bost, B., Sýkora, O. (eds.) SOFSEM 2005. LNCS, vol. 3381, pp. 53–61. Springer, Heidelberg (2005)

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

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)

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