Name
Abstract | ||
|---|---|---|
The crossing number, cr(G), of a graph G is the least number of crossing points in any drawing of G in the plane. According to the Crossing Lemma of M. Ajtai, V. Chvátal, M. Newborn, E. Szemerédi, Theory and Practice of Combinatorics, North-Holland, Amsterdam, New York, 1982, pp. 9–12 and F. T. Leighton, Complexity Issues in VLSI, MIT Press, Cambridge, 1983, the crossing number of any graph with n vertices and e4n edges is at least constant times e3-n2. Apart from the value of the constant, this bound cannot be improved. We establish some stronger lower bounds under the assumption that the distribution of the degrees of the vertices is irregular. In particular, we show that if the degrees of the vertices are d1⩾d2⩾···⩾dn, then the crossing number satisfies \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}\begin{eqnarray*}{\rm{cr}}(G)\geq \frac{c_{1}}{n}\end{eqnarray*}\end{document} with \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}\begin{eqnarray*}{\textstyle\sum\nolimits_{{{i}}={{{1}}}}^{{{n}}}}{{id}}_{{{i}}}^{{{3}}}-{{c}}_{{{2}}}{{n}}^{{{2}}}\end{eqnarray*}\end{document}, and that this bound is tight apart from the values of the constants c1, c20. Some applications are also presented. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 12–21, 2010 |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1002/jgt.v64:1 | Journal of Graph Theory |
Keywords | Field | DocType |
stronger lower bound,number satisfies,f. t. leighton,complexity issues,imbalanced graph,graph g,constant time,m. ajtai,crossing lemma,e. szemer,m. newborn,lower bound,crossing number,plane,satisfiability | Graph theory,Graph,Combinatorics,Crossing number (graph theory),Vertex (geometry),Mathematics | Journal |
Volume | Issue | ISSN |
64 | 1 | 0364-9024 |
Citations | PageRank | References |
1 | 0.37 | 14 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| János Pach | 1 | 2366 | 292.28 |
| József Solymosi | 2 | 138 | 18.64 |
| Gábor Tardos | 3 | 1261 | 140.58 |