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

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

Título:      On the Relationship of Minimum Bisection, 
	     Tree-Width and Grid Minors in Planar Graphs
            
Palestrante: Tina Janne Schmidt
             Zentrum Mathematik
             Technische Universität München

Hora e Data: 14h, sexta-feira, 30 de novembro de 2012

Local:       Sala Multi-usos do Numec

Resumo:

Minimum Bisection  denotes the NP-hard  problem to partition
the vertex  set of  a graph into  two classes of  equal size
while minimizing the number  of edges between those classes.
There is a polynomial time algorithm if a tree decomposition
of  bounded width  is provided.  It is  unknown  whether the
problem remains NP-hard when restricted to planar graphs.

First,  an approach  using separating  vertices in  trees to
construct  a bisection  is presented.  This approach  can be
generalized using  either the Planar Separator  Theorem or a
tree  decomposition.   Together,  these  results  imply  for
planar graphs with bounded  degree that whenever the minimum
bisection width  is large, the  tree-width must be  large as
well.  On the other  hand, large  tree-width does  not imply
large minimum bisection width  in general, but a homogeneity
condition for this implication will be presented.