Graph Drawing with no k Pairwise Crossing EdgesValtr, Pavel (1998) Graph Drawing with no k Pairwise Crossing Edges. In: Graph Drawing 5th International Symposium, GD '97, September 1820, 1997 , pp. 205218(Official URL: http://dx.doi.org/10.1007/3540639381_63). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/3540639381_63
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 xmonotone curves (Jordan arcs).
Actions (login required)
