Electronic Resource
Springer
Combinatorica
17 (1997), S. 427-439
ISSN:
1439-6912
Keywords:
05C10
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
Abstract We show that if a graph ofv vertices can be drawn in the plane so that every edge crosses at mostk〉0 others, then its number of edges cannot exceed 4.108√kv. Fork≤4, we establish a better bound, (k+3)(v−2), which is tight fork=1 and 2. We apply these estimates to improve a result of Ajtai et al. and Leighton, providing a general lower bound for the crossing number of a graph in terms of its number of vertices and edges.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01215922
Permalink
|
Location |
Call Number |
Expected |
Availability |