Turan-type results for topological graphs

Rados Radoicic


December 10,
refreshments at 3:45pm


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 $3n-6$ 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 self-crossing cycle of length four, with further applications. Joint work with subsets of {J. Pach, R. Pinchasi, G. Tardos and G. Toth}.

Speaker's Contact Info: rados(at-sign)math.mit.edu

Return to seminar home page

Combinatorics Seminar, Mathematics Department, MIT, sara(at-sign)math.mit.edu

Page loaded on December 02, 2003 at 12:54 PM. Copyright © 1998-99, Sara C. Billey. All rights reserved.