## Graph Drawing with no k Pairwise Crossing Edges
Valtr, Pavel
(1998)
Full text not available from this repository. ## AbstractA 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 References |