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, Perugia, Italy , pp. 37-46 (Official URL: http://dx.doi.org/10.1007/978-3-540-24595-7_4).

Full text not available from this repository.

Abstract

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
ID Code:425

Repository Staff Only: item control page

References

Aggarwal, A., Klawe, M., Shor, P., Multi-layer grid embeddings for VLSI, Algorithmica 6, (1991), 129-151.

Beineke, L. W., Complete bipartite graphs: Decomposition into planar subgraphs, Chapter 7, in: A Seminar on Graph Theory, (F. Harary, ed.), Selected Topics in Mathematics, Holt, Rinehart and Winston, New York, 1967, 43-53.

Beineke, L. W., Biplanar graphs: A survey, Computers and Mathematics with Applications 34 (1997), 1-8.

Beineke, L. W., Harary, F., Moon, J. W., On the thickness of the complete bipartite graphs, Proc. of the Cambridge Philosophical Society 60 (1964), 1-5.

Czabarka, É., Sýkora, O., Székely, L. A., Vrt'o, I., Biplanar crossing numbers: A survey of results and problems, in: Finite and Infinite Combinatorics, (T. Fleiner, G. O. H. Katona, eds.), Bolyai Society Mathematical Studies, Akadémia Kiadó, Budapest, to appear.

Kleitman, D. J., The crossing number of K_{5,n}, J. Combinatorial Theory 9 (1970), 315-323.

Leighton, T. F., Complexity Issues in VLSI, MIT Press, Cambridge 1983.

Nash-Williams, J. A., Edge disjoint spanning trees of finite graphs, J. London Math. Soc., 36 (1961), 445-450.

Owens, A., On the biplanar crossing number, IEEE Transactions on Circuit Theory 18 (1971), 277-280.

Richter, R. B., Sirán, J., The crossing number of K_{3,n} in a surface, J. Graph Theory 21 (1996), 51-54.

Shahrokhi, F., Sýkora, O., Székely, L. A., Vrt'o, I., The book crossing number of graphs, J. Graph Theory 21 (1996), 413-424.

Sýkora, O., Székely, L. A., Vrt'o, I., Crossing numbers and biplanar crossing numbers: using the probabilistics method, submitted.

Shahrokhi, F., Sýkora, O., Székely, L. A., Vrt'o, I., Bounds for convex crossing numbers, in: Proc. 9th Int. Computing and Combinatorics Conference, Lecture Notes in Computer Science 2697, Springer Verlag, Berlin 2003, 487-495.

Truszczynski, M., Decomposition of graphs into forests with bounded maximum degree, Discrete Mathematics 98 (1991), 207-222.

White A. T., Beineke, L. W., Topological graph theory, in: Selected Topics in Graph Theory, (L. W. Beineke, R. J. Wilson, eds.), Academic Press, New York 1978, 15-50.