An Improved Lower Bound for Crossing Numbers

Djidjev, Hristo and Vrt'o, Imrich (2002) An Improved Lower Bound for Crossing Numbers. In: Graph Drawing 9th International Symposium, GD 2001, September 23-26, 2001, Vienna, Austria , pp. 96-101 (Official URL: http://dx.doi.org/10.1007/3-540-45848-4_8).

Full text not available from this repository.

Abstract

The crossing number of a graph G=(V,E), denoted by cr(G), is the smallest number of edge crossings in any drawing of G in the plane. Leighton [14] proved that for any n-vertex graph G of bounded degree, its crossing number satisfiescr(G) + n = Ω(bw2(G), wherebw(G) is the bisection width of G. The lower bound method was extended for graphs of arbitrary vertex degrees to cr in [15,19], where dv is the degree of any vertex v. We improve this bound by showing that the bisection width can be replaced by a larger parameter - the cutwidth of the graph. Our result also yields an upper bound for the path-width of G in term of its crossing number.

Item Type:Conference Paper
Additional Information:10.1007/3-540-45848-4_8
Classifications:Z Theory > Z.001 General
G Algorithms and Complexity > G.420 Crossings
ID Code:423

Repository Staff Only: item control page

References

Bezrukov, S.L.: Edge Isoperimetric Problems on Graphs. In: Lovász, L., Gyarfás, A., Katona, G.O.H., Recski, A., Székely, L. (eds.): Graph Theory and Combinatorial Biology. Bolyai Soc. Mathematical Studies 7. Akadémia Kiadó, Budapest (1999) 157-197

Bezrukov, S., Chavez, J.D., Harper, L.H., Röttger, M., Schroeder, U.-P.: The Congestion of n-Cube Layout on a Rectangular Grid. Discrete Mathematics 213 (2000) 13-19

Cimikowski, R.: Algorithms for the Fixed Linear Crossing Number Problem. Submitted to Discrete Applied Mathematics

Di Battista, G., Eades, P., Tamassia, R. and Tollis, I.G.: Graph Drawing: Algorithms for the Visualization of Graphs. Prentice-Hall (1999)

Even,G., Guha, S., Schieber, B: Improved Approximations of Crossings in Graph Drawing and VLSI Layout Area. In: 32nd Annual Symposium on Theory of Computing. ACM Press (2000) 296-305

Faria, L., Herrera de Figuerado, C.M.: On Eggleton and Guy conjectured upper bounds for the crossing number of the n-cube. Mathematica Slovaca 50 (2000) 271-287

Garey, M.R., and Johnson, D.S.: Crossing Number is NP-complete, SIAM J. Algebraic and Discrete Methods, 4 (1983) 312-316

Gazit, H., Miller, G.L.: Planar Separators and the Euclidean Norm. In: SIGAL Intl. Symposium on Algorithms. Lecture Notes in Computer Science, Vol. 450. Springer Verlag, Berlin (1990) 338-347

Geelen, J.F., Richter, R.B., Salazar, G.: Embedding Graphs on Surfaces. Submitted to J. Combinatorial Theory-B

Grohe, M.: Computing Crossing Numbers in Quadratic Time. In Proc. 33rd Annual ACM Symposium on Theory of Computing. ACM Press (2001)

Hlinený, P.: Crossing-Critical Graphs and Path-Width. In: 9th Intl. Symposium on Graph Drawing. Lecture Notes in Computer Science, Springer Verlag, Berlin (2001)

Kinnersley, N.: The Vertex Separation Number of a Graph Equals its Path-Width. Information Processing Letters 142 (1992) 345-350

Liebers, A.: Methods for Planarizing Graphs - a Survey and Annotated Bibliography. J. of Graph Algorithms and Applications 5 (2001) 1-74

Leighton, F.T.: Complexity Issues in VLSI, M.I.T. Press, Cambridge (1983)

Pach, J., Shahrokhi, F., Szegedy, M.: Applications of Crossing Number. Algorithmica 16 (1996) 111-117

Purchase, H.: Which Aesthetic has the Greatest Effect on Human Understanding? In: 5th Intl. Symposium on Graph Drawing. Lecture Notes in Computer Science. Vol. 1353. Springer Verlag, Berlin, (1997), 248-261.

Shahrokhi, F., Sýkora, O., Székely, L.A., Vrt'o, I.: Crossing Numbers: Bounds and Applications. In: Bárány, I., Boroczky, K. (eds.): Intuitive Geometry. Bolyai Society Mathematical Studies 6. Akadémia Kiadó, Budapest (1997) 179-206

Sýkora, O., Vrt'o, I.: On the Crossing Number of the Haypercube and the Cube Connected Cycles. BIT 33 (1993) 232-237

Sýkora, O., Vrt'o, I.: On VLSI Layouts of the Star Graph and Related Networks. Integration, The VLSI Journal 17 (1994) 83-93

Wei-Liang Lin, Amir H. Farrahi, A.H., Sarrafzadeh, M.: On the Power of Logic Resynthesis. SIAM J. Computing 29 (2000) 1257-1289