From: Rosa Teorell (rosat@microsoft.com)
Date: Thu Jan 22 2004 - 10:03:35 PST
You are invited to attend...
*****************************************************************************************************
WHO: Rados Radoicic
AFFILIATION: Mass. Institute of Technology
TITLE: Tur\'{a}n-type results for topological graphs
WHEN: Fri 1/23/2004
WHERE: 113/1159 Research Lecture Room, Microsoft Research
TIME: 10:30AM -12:00PM
HOST: Jennifer Chayes/Christian Borgs
******************************************************************************************************
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 $3n-6$ edges. How far can we {\em 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 {\em 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, Chv\'atal, Newborn, Szemer\'edi, 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. T\'oth$\}$.
--------------------------------------------------------------------------
References:
[1] J. Pach, R. Radoicic, and G. Tóth.
Relaxing planarity for topological graphs, Discrete and Computational Geometry (J. Akiyama, M. Kano, eds.) Lecture Notes in Computer Science 2866, Springer-Verlag, Berlin, 2003, 221--232.
[2] R. Pinchasi and R. Radoicic.
Topological graphs with no self-intersecting cycle of length 4. Proceedings of the 19th Annual ACM Symposium on Computational Geometry, 2003, 98--103. Towards a Theory of Geometric Graphs, Contemporary Mathematics, AMS, 2004, to appear.
[3] J. Pach, R. Radoicic and G. Tóth.
A generalization of quasi-planarity. Towards a Theory of Geometric Graphs, Contemporary Mathematics, AMS, 2004, to appear.
[4] J. Pach, R. Radoicic, G. Tóth, and G. Tardos.
Improving the Crossing Lemma by finding more crossings in sparse graphs. submitted.
BIO:
Rados Radoicic is a graduate student at the Department of Mathematics, Massachusetts Institute of Technology (MIT), where he is finishing his Ph.D. thesis under the supervision of Daniel Kleitman (MIT) and Janos Pach (NYU). He received his B.S. in Mathematics with Theoretical Computer Science from MIT in 2000. His research interests include discrete and computational geometry and all other aspects of Erdos-type combinatorics, including Ramsey theory, extremal graph theory, random graphs and the probabilistic method, algorithms and complexity.
_______________________________________________
Theory-group mailing list
Theory-group@cs.washington.edu
http://mailman.cs.washington.edu/mailman/listinfo/theory-group
This archive was generated by hypermail 2.1.6 : Thu Jan 22 2004 - 10:04:13 PST