Bounds and Methods for k-Planar Crossing Numbers

Shahrokhi, Farhad and Sýkora, Ondrej and Székely, László A. and Vrt'o, Imrich (2004) Bounds and Methods for k-Planar Crossing Numbers. In: Graph Drawing 11th International Symposium, GD 2003, September 21-24, 2003 , pp. 37-46(Official URL:

Full text not available from this repository.


The k-planar crossing number of a graph is the minimum number of crossings of its edges over all possible drawings of the graph in k planes. We propose algorithms and methods for k-planar drawings of general graphs together with lower bound techniques. We give exact results for the k-planar crossing number of K_{2k+1,q}, for k >= 2. We prove tight bounds for complete graphs.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-540-24595-7_4
Classifications: G Algorithms and Complexity > G.420 Crossings

Actions (login required)

View Item View Item