Graphs Drawn with Few Crossings per Edge

Pach, János and Tóth, Géza (1997) Graphs Drawn with Few Crossings per Edge. In: Symposium on Graph Drawing, GD '96, September 18-20, 1996 , pp. 345-354(Official URL:

Full text not available from this repository.


We show that if a graph of v vertices can be drawn in the plane so that every edge crosses at most k>0 others, then its number of edges cannot exceed 4.108 \sqrt{kv}. For k<=4, we establish a better bound, (k+3)(v-2), which is tight for k=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 naumber of a graph in terms of its number of vertices and edges.

Item Type: Conference Paper
Additional Information: 10.1007/3-540-62495-3_59
Classifications: Z Theory > Z.999 Others
G Algorithms and Complexity > G.420 Crossings

Actions (login required)

View Item View Item