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.

Abstract

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

Repository Staff Only: item control page

References

R. Adamec, M. Klazar, and P. Valtr, Generalized Davenport-Schinzel sequences with linear upper bound, Discrete Math. 108 (1992), 219-229.

P.K. Agarwal, B. Aronov, J. Pach, R. Pollack, and M. Sharir, Quasi-planar graphs have a linear number of edges, Graph Drawing (Passau, 1995), Lecture Notes in Comput. Sci. 1027 (1995), 1-7.

H. Davenport and A. Schnizel, A combinatorial problem connected with different equations, Amer. J. Math. 87 (1965), 684-694.

R. Dilworth, A decomposition theorem for partially ordered sets, Annals of Mathematics 51 (1950), 161-166.

P. Erdös and G. Szekeres, A combinatorial problem in geometry, Compositio Math. 2 (1935), 463-470.

M. Klazar and P. Valtr, Generalized Davenport-Schinzel sequences, Combinatorica 14 (1994), 463-476.

J. Pach, Notes on geometric graph theory, in: Discrete and Computational Geometry: Papers from DIMACS Series, Vol. 6, AMS, Providence, RI, 1991, pp. 273-285.

J. Pach and P.K. Agarwal, Combinatorial Geometry, Wiley Interscience, New York (1995).

J. Pach, F. Sharokhi, and M. Szegedy, Applications of the crossing number, Algorithmica 16 (1996), 111-117.

J. Pach and J. Töröcsik, Some geometric applications of Dilworth's theorem, Discrete Comput. Geom. 12 (1994), 1-7.

F.P. Ramsey, On a problem of a formal logic, Proc. Lond. Math. Soc., II. Ser., 30 (1930), 264-286.

P. Valtr, On geometric graphs with no k pairwise parallel edges, to appear in Discrete and Computational Geometry.