Fox, Jacob and Tóth, Csaba D. (2007) On the Decay of Crossing Numbers. [Conference Paper]
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 |
|---|---|
| Classifications: | G Algorithms and Complexity > G.420 Crossings Z Theory > Z.999 Others |
| ID Code: | 772 |
| Deposited By: | GDEA, Administration |
| Deposited On: | 04 May 2007 |
| Last Modified: | 18 May 2009 13:07 |
| Alternative Locations: | http://www.springer.com/dal/home/computer/lncs?SGWID=1-164-22-173721109-0 |
Repository Staff Only: item control page
