2004 | OriginalPaper | Buchkapitel
Bounds and Methods for k-Planar Crossing Numbers
Autoren: Farhad Shahrokhi, Ondrej Sýkora, Laszlo A. Székely, Imrich Vrt’o
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
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 K2 k + 1, q, for k ≥ 2. We prove tight bounds for complete graphs.