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, Rome, Italy , pp. 205-218 (Official URL: http://dx.doi.org/10.1007/3-540-63938-1_63).
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).
Repository Staff Only: item control page