On the Decay of Crossing Numbers

Fox, Jacob and Tóth, Csaba D. (2007) On the Decay of Crossing Numbers. In: Graph Drawing 14th International Symposium, GD 2006, September 18-20, 2006, Karlsruhe, Germany , pp. 174-183 (Official URL: http://dx.doi.org/10.1007/978-3-540-70904-6_18).

Full text not available from this repository.

Abstract

The crossing number \cn(G) of a graph G is the minimum number of crossings over all drawings of G in the plane. In 1993, Richter and Thomassen [13] conjectured that there is a constant c such that every graph G with crossing number k has an edge e such that \cn(G-e) \geq k-c\sqrt{k}. They showed only that G always has an edge e with \cn(G-e) \geq \frac{2}{5}\cn(G)-O(1). We prove that for every fixed \epsilon>0, there is a constant n_0 depending on \epsilon such that if G is a graph with n>n_0 vertices and m>n^{1+\epsilon} edges, then G has a subgraph G' with at most (1-\frac{1}{24\epsilon})m edges such that \cn(G') \geq (\frac{1}{28}-o(1))\cn(G).

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-70904-6_18
Classifications:G Algorithms and Complexity > G.420 Crossings
Z Theory > Z.999 Others
ID Code:772

Repository Staff Only: item control page

References

M. Ajtai, V. Chvatal, M. Newborn, and E. Szemeredi: Crossing-free subgraphs, in Theory and Practice of Combinatorics, vol. 60 of Mathematical Studies, North-Holland, Amsterdam, 1982, pp. 9-12.

P. Erdös and M. Simonovits: Compactness results in extremal graph theory, Combinatorica 2 (1982), 275-288.

H. Gazit and G. L. Miller: Planar separators and the Euclidean norm, in SIGAL International Symposium on Algorithms, vol. 450 of LNCS, Springer-Verlag, Berlin, 1990, pp. 338-347.

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

T. Leighton: New lower bound techniques for VLSI, Math. Systems Theory 17 (1984), 47-70.

R. J. Lipton and R. E. Tarjan: A separator theorem for planar graphs, SIAM J. Appl. Math. 36 (1979), 177-189.

H. Nagamochi and T. Ibaraki: A linear-time algorithm for nding a sparse k-connected spanning subgraph of a k-connected graph, Algorithmica 7 (1992), 583-596.

J. Pach, R. Radoicic, G. Tardos, and G. Toth: Improving the Crossing Lemma by nding more crossings in sparse graphs, in 20th ACM Symposium on Computational Geometry, ACM Press, New York, 2004, pp. 68-75.

J. Pach, F. Shahrokhi, and M. Szegedy: Applications of the crossing number, Algorithmica 16 (1996), 111-117.

J. Pach, J. Solymosi, and G. Tardos: Crossing numbers of imbalanced graphs, lecture presented at SIAM Conf. Discrete Math. (Victoria, BC, 2006).

J. Pach, J. Spencer, and G. Toth: New bounds on crossing numbers, Discrete Comput. Geom. 24 (2000), 623-644.

J. Pach and G. Toth: Thirteen problems on crossing numbers, Geombinatorics 9 (2000), 194-207.

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

G. Salazar: On a crossing number result of Richter and Thomassen, J. Combin. Theory Ser. B 79 (2000), 98-99.

F. Shahrokhi, O. Sykora, L. A. Szekely, and I. Vrto: Crossing numbers: bounds and applications, in Intuitive geometry (Budapest, 1995), 179-206, vol. 6 of Bolyai Soc. Math. Stud., Janos Bolyai Math. Soc., Budapest, 1997.

L. A. Szekely: A successful concept for measuring non-planarity of graphs: the crossing number, Discrete Math. 276 (2004), 331-352.

L. A. Szekely: Short proof for a theorem of Pach, Spencer, and Toth, in Towards a theory of geometric graphs, vol. 342 of Contemp. Math., AMS, Providence, RI, 2004, pp. 281-283.