Logo

Login | Create Account

Graph Drawing with no k Pairwise Crosseing Edges

Valtr, Pavel (1998) Graph Drawing with no k Pairwise Crosseing Edges. [Conference Paper]

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
Classifications:G Algorithms and Complexity > G.420 Crossings
G Algorithms and Complexity > G.560 Geometry
ID Code:80
Deposited By:Martinez Leon, Victoria
Deposited On:02 Nov 2004
Last Modified:18 Sep 2008 13:08

Repository Staff Only: item control page

References

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

2. 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.

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

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

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

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

7. 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.

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

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

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

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

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

GDEA is powered by EPrints 3 which is developed by the School of Electronics and Computer Science at the University of Southampton. More information and software credits.