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 , 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
URI:	http://gdea.informatik.uni-koeln.de/id/eprint/1435

Actions (login required)

View Item