An improved lower bound for crossing numbers
UNSPECIFIED (2002) An improved lower bound for crossing numbers. In: 9th International Symposium on Graph Drawing (GD 2001), SEP 23-26, 2001, VIENNA, AUSTRIA.Full text not available from this repository.
The crossing number of a graph G = (V, E), denoted by cr(G), is the smallest number of edge crossings in any drawing of G in the plane. Leighton  proved that for any n-vertex graph G of bounded degree, its crossing number satisfies cr(G) + n = Omega(bw(2) (G)), where bw(G) is the bisection width of G. The lower bound method was 2 extended for graphs of arbitrary vertex degrees to cr(G) + (1)/(16) Sigma(nuis an element ofG) d(nu)(2) Omega(bw(2) (G)) in [15,19], where d(nu) 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 Item (UNSPECIFIED)|
|Subjects:||Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software|
|Series Name:||LECTURE NOTES IN COMPUTER SCIENCE|
|Journal or Publication Title:||GRAPH DRAWING|
|Editor:||Mutzel, P and Junger, M and Leipert, S|
|Number of Pages:||6|
|Page Range:||pp. 96-101|
|Title of Event:||9th International Symposium on Graph Drawing (GD 2001)|
|Location of Event:||VIENNA, AUSTRIA|
|Date(s) of Event:||SEP 23-26, 2001|
Actions (login required)