Graph Drawing with no k Pairwise Crossing Edges

Valtr, Pavel (1998) Graph Drawing with no k Pairwise Crossing Edges. In: Graph Drawing 5th International Symposium, GD '97, September 18-20, 1997 , pp. 205-218(Official URL:

Full text not available from this repository.


A geometric graph is a graph G=(V,E) drawn in the plane so that the vertex set V consists of points in general position and the edge set E consists of straight line segments between points of V. It is known that, for any fixed k, any geometric graph G on n vertices with no k pairwise crossing edges contains at most O(n log n) edges. In this paper we give a new, simpler proof of this bound, and show that the same bound hold also when the edges of G are represented by x-monotone curves (Jordan arcs).

Item Type: Conference Paper
Additional Information: 10.1007/3-540-63938-1_63
Classifications: G Algorithms and Complexity > G.420 Crossings
G Algorithms and Complexity > G.560 Geometry

Actions (login required)

View Item View Item