Department of Computer Science | Institute of Theoretical Computer Science | CADMO

Prof. Emo Welzl and Prof. Bernd Gärtner

Mittagsseminar Talk Information |

**Date and Time**: Thursday, July 16, 2015, 12:15 pm

**Duration**: 30 minutes

**Location**: OAT S15/S16/S17

**Speaker**: Andres Ruiz-Vargas (EPF Lausanne)

A simple topological graph is a graph drawn in the plane so that its edges are represented by continuous arcs with the property that any two of them meet at most once. In this talk, we present a lemma for constructing plane subgraphs in simple topological graphs. We will discuss the following two applications of this lemma.

Let $G$ be a complete simple topological graph on $n$ vertices. The three edges induced by any triplet of vertices in $G$ form a simple closed curve. If this curve contains no vertex in its interior (exterior), then we say that the triplet forms an empty triangle. In 1998, Harborth proved that $G$ has at least 2 empty triangles, and he conjectured that the number of empty triangles is at least $2n/3$. We settle Harborth's conjecture in the affirmative.

We also sketch a proof that every complete simple topological graph on $n$ vertices contains $\Omega(n^\frac 12)$ pairwise disjoint edges.

Upcoming talks | All previous talks | Talks by speaker | Upcoming talks in iCal format (beta version!)

Previous talks by year: 2024 2023 2022 2021 2020 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M | admin login