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.

Abstract

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 [14] 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
Publisher:	SPRINGER-VERLAG BERLIN
ISBN:	3-540-43309-0
ISSN:	0302-9743
Editor:	Mutzel, P and Junger, M and Leipert, S
Date:	2002
Volume:	2265
Number of Pages:	6
Page Range:	pp. 96-101
Publication Status:	Published
Title of Event:	9th International Symposium on Graph Drawing (GD 2001)
Location of Event:	VIENNA, AUSTRIA
Date(s) of Event:	SEP 23-26, 2001
URI:	http://wrap.warwick.ac.uk/id/eprint/10011

Data sourced from Thomson Reuters' Web of Knowledge

Request changes to a record

Actions (login required)

View Item