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, Berkeley, California, USA , pp. 345-354 (Official URL: http://dx.doi.org/10.1007/3-540-62495-3_59).

Full text not available from this repository.

Abstract

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
ID Code:112

Repository Staff Only: item control page

References

M. Ajtai, V. Chvátal, M. Newborn, E. Szemerédi. Crossing-free subgraphs. Ann. Discrete Mathematics 12 (1982), 9-12.

K. Clarkson, H. Edelsbrunner, L. Guibas, M. Sharir, E. Welzl. Combinatorial complexity bounds for arrangements of curves and surfaces. Discrete and Computational Geometry 5 (1990), 99-160.

G.H. Hardy, E.M. Wright. An Introduction to the Theory of numbers. University Press, Oxford, 1954.

T. Leighton. Complexity Issues in VLSI. Foundation of Computing Series, MIT Press, Cambridge, MA, 1983.

J. Pach and P.K. Agarwal. Combinatorial geometry. John Wiley, New-York, 1995.

J. Pach and M. Sharir. On the number of incidences between points and curves. Combinatorics, Probability, and Computing, submitted.

J. Spencer, personal communication.

L. Székely, Crossing numbers and hard Erdös problems in diskrete geometry. Combinatorics, Probability, and Computing, to appear.

E. Szemerédi and W.T. Trotter. Extremal problems in discrete geometry. Combinatorica 3 (1983), 381-392.