Noon lecture

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

On 21.05.2009 at 12:20 in S6, there is the following noon lecture:

Extending partial plane embeddings

Vít Jelínek

Abstract

(joint work with Jan Kratochvil, Maurizio Patrignani, and Ignaz Rutter)

The topic of my talk is the following decision problem, called PREEMBEDDED PLANARITY:

Input: a graph H with a prescribed plane embedding, and a graph G that contains H as a subgraph. Question: is it possible to extend the prescribed embedding of H into a plane embedding of the whole graph G?

I will present a polynomial-time algorithm that solves this decision problem. The main tool of the algorithm is the data structure known as SPQR tree, which allows to concisely represent all possible embeddings of a given planar graph. I will also mention several optimization problems related to PREEMBEDDED PLANARITY, which turn out to be NP-complete.

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