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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
M. Ajtai, V. Chvátal, M. Newborn, andE. Szemerédi: Crossing-free subgraphs,Ann. Discrete Mathematics,12 (1982), 9–12.
K. Clarkson, H. Edelsbrunner, L. Guibas, M. Sharir, andE. Welzl: Combinatorial complexity bounds for arrangements of curves and surfaces,Discrete and Computational Geometry,5 (1990), 99–160.
G. H. Hardy andE. M. Wright:An Introduction to the Theory of Numbers, University Press, Oxford, 1954.
T. Leighton:Complexity Issues in VLSI, Foundations, of Computing Series, MIT Press, Cambridge, MA, 1983.
J. Pach andP. K. Agarwal:Combinatorial Geometry, John Wiley, New York, 1995.
J. Pach andM. Sharir: On the number of incidences between points and curves,Combinatorics, Probability, and Computing, to appear.
J. Spencer: A midrange crossing constant manuscript, 1997.
L. Székely: Crossing numbers and hard Erdős problems in discrete geometry,Combinatorics, Probability, and Computing, to appear.
E. Szemerédi andW. T. Trotter: Extremal problems in discrete geometry,Combinatorica,3 (1983), 381–392.
Author information
Authors and Affiliations
Additional information
Supported by NSF grant CCR-94-24398 and PSC-CUNY Research Award 667339.
Supported by OTKA-T-020914, OTKA-F-22234 and the Margaret and Herman Sokol Postdoctoral Fellowship Award.
Rights and permissions
About this article
Cite this article
Pach, J., Tóth, G. Graphs drawn with few crossings per edge. Combinatorica 17, 427–439 (1997). https://doi.org/10.1007/BF01215922
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01215922