Turantype results for topological graphsRados RadoicicMIT
December 10,

ABSTRACT


A geometric (topological) graph is a graph drawn in the plane so that its vertices are represented by points and its edges by segments (curves) connecting the corresponding points. It follows from Euler's formula that every geometric (topological) graph with no two crossing edges has at most $3n6$ edges. How far can we relax this simple condition so that it still implies that we have at most a linear number of edges? I will survey some known results and open problems on this subject. Among others, I will estimate the maximum number of edges of a geometric (topological) graph if there is no edge crossed by 2, 3, 4, and in general, by $k$ edges. I will also sketch the proof that if we do not have three pairwise crossing edges, then we still have a linear number of edges. As an application, I show how this is connected, through the well known Crossing Lemma of Ajtai, Chvatal, Newborn, Szemeredi, and Leighton, to many problems in discrete and computational geometry. If the time allows, I will also sketch the proof that any topological graph on $n$ vertices and $\Omega (n^{8/5})$ edges contains a selfcrossing cycle of length four, with further applications. Joint work with subsets of {J. Pach, R. Pinchasi, G. Tardos and G. Toth}. 
Combinatorics Seminar, Mathematics Department, MIT, sara(atsign)math.mit.edu 

