Autores

1699
414,257
1700
414,257

Informações:

Publicações do PESC

Título
Alguns Resultados em Invariantes de não Planaridade em Grafos: Uma Abordagem Estrutural e de Complexidade
Linha de pesquisa
Algoritmos e Combinatória
Tipo de publicação
Tese de Doutorado
Número de registro
Data da defesa
4/8/1998
Resumo
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.
Abstract
In this thesis we study four invariants of nonplanarity in graphs. The minimum number of crossings of edges for a drawing in the plane (crossing number), the maximum number of edges in a planar subgraph (maximum planar subgraph), the minimum number of edges whose removal obtains a planar graph (skewness) and the minimum number of splittings of vertices that obtains a planar graph (splitting number). We study these invariants for the class of the n-cube graphs. We prove that the splitting number of the 4-cube is 4. And we use this fact to exhibit a lower bound for the splitting number of the n-cube. We exhibit an upper bound for the crossing number of the n-cube improving the upper bound of Madej, the only known upper bound for the crossing number of the n-cube. And we prove that the conjecture of Guy and Erdös for the crossing number of the n-cube holds for the 6-, 7- and 8-cubes. We prove that the corresponding decision problem versions for splitting number, skewness and maximum planar subgraph are NP-complete for cubic graphs. We prove that the corresponding optimization problem versions for splitting number and skewness are MAX SNP-hard for cubic graphs.
Arquivo
Topo