On topological graphs with at most four crossings per edge
Author:
Preprint
Abstract
We show that if a graph $G$ with $n \geq 3$ vertices can be drawn in the plane such that each of its edges is involved in at most four crossings, then $G$ has at most $6n-12$ edges. This settles a conjecture of Pach, Radoi\v{c}i\'{c}, Tardos, and T\'oth, and yields a better bound for the famous Crossing Lemma: The crossing number, $\mbox{cr}(G)$, of a (not too sparse) graph $G$ with $n$ vertices and $m$ edges is at least $c\frac{m^3}{n^2}$, where $c > 1/29$. This bound is known to be tight, apart from the constant $c$ for which the previous best lower bound was $1/31.1$. As another corollary we obtain some progress on the Albertson conjecture: Albertson conjectured that if the chromatic number of a graph $G$ is $r$, then $\mbox{cr}(G) \geq \mbox{cr}(K_r)$. This was verified by Albertson, Cranston, and Fox for $r \leq 12$, and for $r \leq 16$ by Bar\'at and T\'oth. Our results imply that Albertson conjecture holds for $r \leq 18$.
Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- On the Maximum Number of Edges in Topological Graphs with no Four Pairwise Crossing EdgesDiscrete & Computational Geometry, 2009
- Crossings, Colorings, and CliquesThe Electronic Journal of Combinatorics, 2009
- On the maximum number of edges in quasi-planar graphsJournal of Combinatorial Theory, Series A, 2007
- Improving the Crossing Lemma by Finding More Crossings in Sparse GraphsDiscrete & Computational Geometry, 2006
- An improvement of the crossing number boundJournal of Graph Theory, 2005
- Research Problems in Discrete Geometry2005
- Proofs from The BOOKThe American Mathematical Monthly, 2000
- Graphs drawn with few crossings per edgeCombinatorica, 1997
- Crossing-Free Subgraphs1982
- A Theorem of R. L. Brooks and a Conjecture of H. HadwigerProceedings of the London Mathematical Society, 1957