# Noon lecture

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

On 03.12.2009 at 12:20 in corridor, there is the following noon lecture:

# Construction sequences of 3-connected graphs

## Jens M. Schmidt

## Abstract

Tutte proved 1961 that every 3-connected graph on more than 4 nodes has a contractible edge. Barnette and Grünbaum proved 1969 the existence of a removable edge in the same setting. We show that the sequence of contractions and the sequence of removals from G to the K_4 can be computed in O(|V|^2) time by extending Barnette and Grünbaum's theorem. As an application, we derive a certificate for the 3-connectedness of graphs that can be easily computed and verified.

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