Djidjev, Hristo and Vrt'o, Imrich (2002) An Improved Lower Bound for Crossing Numbers. [Conference Paper]
Full text not available from this repository.
Abstract
The crossing number of a graph $G=(V,E)$, denoted by ${\rm cr}(G),$ is the smallest number of edge crossings in any drawing of $G$ in the plane. Leighton [14] proved that for any $n$-vertex graph $G$ of bounded degree, its crossing number satisfies ${\rm cr}(G)+n=\Omega({\rm bw}^2(G))$, where ${\rm bw}(G)$ is the bisection width of $G$. The lower bound method was extended for graphs of arbitrary vertex degrees to ${\rm cr}(G)+\frac{1}{16} \sum_{v\in G}{d_v^2}= \Omega({\rm bw}^2(G))$ in [15,19], where dv is the degree of any vertex $v$. We improve this bound by showing that the bisection width can be replaced by a larger parameter - the cutwidth of the graph. Our result also yields an upper bound for the path-width of $G$ in term of its crossing number.
| Item Type: | Conference Paper |
|---|---|
| Classifications: | Z Theory > Z.001 General G Algorithms and Complexity > G.420 Crossings |
| ID Code: | 423 |
| Deposited By: | Martinez Leon, Victoria |
| Deposited On: | 21 Dec 2004 |
| Last Modified: | 18 Sep 2008 13:08 |
| Alternative Locations: | http://www.springerlink.com/openurl.asp?genre=article&issn=0302-9743&volume=2265&spage=96 |
Repository Staff Only: item control page
