Noon lecture

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

On 13.03.2008 at 12:20 in S1, there is the following noon lecture:

Untangling planar graphs

Josef Cibulka

MFF

Abstract

Untangling is a process in which some vertices in a planar drawing of a graph are moved to obtain a straight-line planar drawing. The aim is to move as few vertices as possible. I will present an algorithm that untangles any drawing of the cycle graph C_n while keeping at least \Omega(n^{2/3}) vertices fixed. In the rest of the talk, I will sketch a proof of an upper bound on the number of fixed vertices in the worst case. For any given planar graph G, the bound is a function of the number of vertices, maximum degree and diameter of G. One of its consequences is the upper bound O((n log n)^{2/3}) for all 3-vertex-connected planar graphs on n vertices.

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

Webmaster: kamweb.mff.cuni.cz         Modified: 19. 10. 2010