Computational Geometry Seminar

Wednesday, April 5th, 2006, 16:10-18:00

Room 309
Schreiber Building

On the maximum number of edges in k-quasi-planar graphs

Eyal Ackerman, Technion

A topological graph is called \emph{$k$-quasi-planar}, if it does not contain $k$ pairwise crossing edges. It is conjectured that for every fixed $k$ the maximum number of edges in a $k$-quasi-planar graph on $n$ vertices is $O(n)$. We provide, for the first time, an affirmative answer to the case $k=4$. We also give the simplest proof and the best upper bound known, for the maximum number of edges in 3-quasi-planar graphs on $n$ vertices. Moreover, we show a tight upper bound for 3-quasi-planar graphs in which every pair of edges meet at most once.

Joint work with Gabor Tardos.