Improvement on the Decay of Crossing Numbers

Cerný, Jakub and Kyncl, Jan and Tóth, Géza (2008) Improvement on the Decay of Crossing Numbers. In: Graph Drawing 15th International Symposium, GD 2007, September 24-26, 2007, Sydney, Australia , pp. 25-30 (Official URL: http://dx.doi.org/10.1007/978-3-540-77537-9_5).

Full text not available from this repository.

Abstract

We prove that the crossing number of a graph decays in a "continuous fashion" in the following sense. For any varepsilon>0 there is a delta>0 such that for n sufficiently large, every graph G with n vertices and mge n^1+varepsilon edges has a subgraph G' of at most (1-delta)m edges and crossing number at least (1-varepsilon)cro(G). This generalizes the result of J. Fox and Cs. Tóth.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-77537-9_5
Classifications:G Algorithms and Complexity > G.420 Crossings
ID Code:825

Repository Staff Only: item control page

References

N. Alon, S Hoory, N. Linial: The Moore bound for irregular graphs, Graphs and Combinatorics 18 (2002), 53-57.

J. Fox, Cs. Tóth: On the decay of crossing numbers, Proc. 14th Symposium on Graph Drawing (Karlsruhe, 2006), Lecture Notes in Computer Science 4372, Springer-Verlag, Berlin, 174-183.

T. Leighton: Complexity issues in VLSI, MIT Press, Cambridge, MA, 1983.

J. Pach, R. Radoicić, G. Tardos, G. Tóth: Improving the Crossing Lemma by finding more crossings in sparse graphs, Proc. 19th ACM Symposium on Computational Geometry 2004, 68-75. Also in: Discrete and Computational Geometry 36 (2006), 527-552.

J. Pach, G. Tóth: Thirteen problems on crossing numbers, Geombinatorics 9 (2000), 194-207.

B. Richter, C. Thomassen: Minimal graphs with crossing number at least k, J. Combin. Theory Ser. B 58 (1993), 217-224.

F. Shahrokhi, O. Sýkora, L. Székely, I. Vrto: Crossing numbers: bounds and applications, in: Intuitive geometry (Budapest, 1995), Bolyai Soc. Math. Stud. 6 Budapest, 1997, 179-206.

L. Székely: Short proof for a theorem of Pach, Spencer, and Tóth, in: Towards a theory of geometric graphs, Contemporary Mathematics 342, AMS, Providence, RI, 2004, 281-283.