ICM 1998, Berlin, Aug. 18–27

Abstracts of Short Communications and Posters

Section:

13. Combinatorics

1991 MS Classification: 5 Valtr, Pavel, Charles University, Prague, Czech Republic Geometric applications of generalized Davenport–Schinzel sequences A geometric graph drawn in the plane so that vertices are represented by distinct points in general position and edges by staight-line segments connecting corresponding pairs of points. We show that a linear upper bound on the length of generalized Davenport–Schinzel sequences with a certain forbidden pattern implies the following results. If a geometric graph on n vertices contains no k pairwise (internally) crossing edges, then it has at most c_{k}n log n edges. If a geometric graph on n vertices contains no k pairwise parallel edges, then it has at most c_{k}n edges (two edges are parallel, if they are disjoint and the convex hull of their union is a quadrilateral).