ISSN:
1432-0444
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract. The crossing number , cr(G) , of a graph G is the least number of crossing points in any drawing of G in the plane. Denote by κ(n,e) the minimum of cr(G) taken over all graphs with n vertices and at least e edges. We prove a conjecture of Erdos os and Guy by showing that κ(n,e)n 2 /e 3 tends to a positive constant as n→∈fty and n l e l n 2 . Similar results hold for graph drawings on any other surface of fixed genus. We prove better bounds for graphs satisfying some monotone properties. In particular, we show that if G is a graph with n vertices and e≥ 4n edges, which does not contain a cycle of length four (resp. six ), then its crossing number is at least ce 4 /n 3 (resp. ce 5 /n 4 ), where c〉0 is a suitable constant. These results cannot be improved, apart from the value of the constant. This settles a question of Simonovits.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/s004540010011
Permalink