A Crossing Lemma for the Pair-Crossing Number

Ackerman, Eyal and Schaefer, Marcus (2014) A Crossing Lemma for the Pair-Crossing Number. In: Graph Drawing 22nd International Symposium, GD 2014, September 24-26, 2014, Würzburg, Germany , pp. 222-233 (Official URL: http://dx.doi.org/10.1007/978-3-662-45803-7_19).

Full text not available from this repository.

Abstract

The pair-crossing number of a graph G, pcr(G), is the minimum possible number of pairs of edges that cross each other (possibly several times) in a drawing of G. It is known that there is a constant c ≥ 1/64 such that for every (not too sparse) graph G with n vertices and m edges pcr(G)≥c(m^3/n^2) . This bound is tight, up to the constant c. Here we show that c ≥ 1/34.2 if G is drawn without adjacent crossings.

Item Type:Conference Paper
Additional Information:10.1007/978-3-662-45803-7_19
Classifications:G Algorithms and Complexity > G.420 Crossings
M Methods > M.999 Others
Z Theory > Z.750 Topology
ID Code:1435

Repository Staff Only: item control page

References

Ackerman, E.: On topological graphs with at most four crossings per edge (manuscript)

Ackerman, E., Tardos, G.: On the maximum number of edges in quasi-planar graphs. J. Combinatorial Theory, Ser. A 114(3), 563–571 (2007)

Aigner, M., Ziegler, G.: Proofs from the Book. Springer, Heidelberg (2004)

Ajtai, M., Chvátal, V., Newborn, M., Szemerédi, E.: Crossing-free subgraphs. In: Theory and Practice of Combinatorics. North-Holland Math. Stud., vol. 60, pp. 9–12. North-Holland, Amsterdam (1982)

Cranston, D.W., West, D.B.: A guide to discharging (manuscript)

Leighton, F.T.: Complexity Issues in VLSI: Optimal Layouts for the Shuffle-Exchange Graph and Other Networks. MIT Press, Cambridge (1983)

Matoušsek, J.: Near-optimal separators in string graphs, ArXiv (February 2013)

Montaron, B.: An improvement of the crossing number bound. J. Graph Theory 50(1), 43–54 (2005)

Pach, J., Radoičić, R., Tardos, G., Tóth, G.: Improving the crossing lemma by finding more crossings in sparse graphs. Disc. Compu. Geometry 36(4), 527–552 (2006)

Pach, J., Tóth, G.: Graphs drawn with few crossings per edge. Combinatorica 17(3), 427–439 (1997)

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)

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

Schaefer, M.: The graph crossing number and its variants: A survey. Electronic Journal of Combinatorics, Dynamic Survey 21 (2013)

Schaefer, M., Štefankovič, D.: Decidability of string graphs. J. Comput. System Sci. 68(2), 319–334 (2004)