Alguns Resultados em Invariantes de não Planaridade em Grafos: Uma Abordagem Estrutural e de Complexidade

Nesta tese nós estudamos quatro invariantes de não planaridade em grafos. 0 número mínimo de cruzamentos de arestas para um desenho no plano (crossing number), o número máxlmo de arestas em um subgrafo planar (maximum planar subgraph), o número mínimo de arestas cuja remoção obtém um grafo planar (skewness) e o número mínimo de "divisões" de vértices, em pares de vértices não adjacentes, que obtém um grafo planar (splittting number). Nós estudamos estes invariantes para a classe dos grafos n-cubos. Nós provamos que o splitting number do 4-cubo é 4. Nós usamos este resultado para exibir um limite inferior para o splitting number do n-cubo. Nós exibimos um limite superior para o crossing number do n-cubo melhorando o limite superior de Madej, o úinico limite superior conhecido para o crossing number do n-cubo. E nós provamos que a conjectura de Guy e Erdös para o crossing number do n-cubo é válida para os 6-, 7- e 8-cubos. Nós provamos que as versões de decisão dos problemas splitting number, skewness e maximum planar subgraph são NP-completas para grafos cúbicos. Nós provamos que as versões de otimização dos problemas splitting number e skewness são MAX SNP-difíceis para grafos cúbicos.