============================================================
   Seminário de Teoria da Computação e Combinatória (TCC)

============================================================

Título:      Three-connectivity and its uses

Palestrante: U. S. R. Murty 
             University of Waterloo

Hora e Data: 14h00, quarta-feira, 11 de novembro de 2009

Local:       Auditório do NUMEC

Resumo:

The notion of  connectivity arises naturally in applications
of  graph  theory.   Thus,   for  example,  the  higher  the
connectivity of a communication  network is, the more secure
and  fault­tolerant it  is. But  connectivity considerations
also play important roles  in understanding the structure of
graphs,  and  in designing  algorithms.  For instance,  most
known proofs  of Kuratowski's Theorem rely  on properties of
3-connected  graphs.  Many famous  conjectures  such as  the
Cycle Double Cover Conjecture, and the 5-Flow Conjecture may
be  reduced to  3-connected graphs.  At a  very  much deeper
level, variants of the notion of connectivity form the basis
of the theory of graph  minors.  My objective in this survey
talk is  to describe certain ways  of generating 3-connected
graphs and  indicate some applications. I hope  to cover the
following topics.

  1. Subdivisions
     Edge-extensions
     Kelmans' decomposition
     Application: Planarity Algorithm

  2. Contractible edges
     Thomassen's lemma.
     Application: Kuratowski's theorem.

  3. Minors
     Vertex-splitting
     Tutte-Seymour-Negami decomposition.
     Application: Wagner's theorem (a precursor to graph minor theory)