Ata de Aula: 23/10/2002
Redator: Sílvia Cristina de Matos Soares
6.3 Parameters of Planarity (Parâmetros de Planaridade)
Objetivo do capítulo: estudar parâmetros que medem quanto um grafo não é planar.
Teorema das 5 cores: todo grafo planar é 5-colorável (a coloração é referente aos vértices).
Teorema das 4 cores: todo grafo planar é 4-colorável (a coloração é referente aos vértices).
Cadeia de Kempe: em um grafo plano propriamente colorido, é um caminho onde as cores se alternam entre duas cores.
Espessura de um grafo: é o número mínimo de grafos planares em uma decomposição de G em grafos planares. Em uma decomposição, cada aresta deve estar exatamente em um grafo.
Número de cruzamentos: é o número mínimo de cruzamentos encontrados quando for feito o desenho do grafo G no plano.
Genus de uma superfície: é o número de alças adicionadas a uma esfera para obtenção da superfície.
Genus de um grafo:
e o número mínimo de alças que preciso colocar em uma esfera para obtenção de uma superfície onde o grafo seja imersível.Abaixo vemos uma imersão do K3,3 no toro (superfície de genus 1). Neste desenho, deve-se considerar que a aresta marcada com "1" dá a volta por trás no toro, no sentido vertical, e o mesmo acontece com a aresta "2", no sentido horizontal.
Teorema dos grafos menores: em uma lista infinita de grafos, algum grafo é o menor de outro. Um grafo é menor de outro se ele for obtido através da deleção e/ou contração de arestas do outro.