Noon lecture

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

On 24.9.2018 at 12:30 in S6, there is the following noon lecture:

Embeddability of Graphs and 2-dimensional Simplicial Complexes

Rado Fulek

IST Austria

Abstract

A 2-dimensional simplicial complex K is orientably \emph{thickenable} if K embeds into some orientable 3-dimensional manifold which is not fixed in advance. By a result of A. Skopenkov (1994), testing orientable thickenability is in NP, but neither NP-hardness nor the existence of a polynomial time algorithm was established to the best of our knowledge. We show that some constrained variants of planarity testing, whose complexity status is unknown, can be reduced in polynomial time to testing orientable thickenability of 2-dimensional simplicial complexes. Additionally, we present a polynomial time algorithm for orientable thickenability in interesting special cases and discuss possible extensions of our results.

Parts of the talk are based on a joint work with J. Kyncl.

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

Webmaster: kamweb.mff.cuni.cz         Archive page