Orientador: Candido Ferreira Xavier de Mendonça NetoDissertação (mestrado) - Universidade Estadual de Campinas, Instituto de ComputaçãoResumo: O splitting number de um grafo G consiste no número mínimo de operações de quebra de vértice que devem ser realizadas em G para produzir um grafo planar, onde uma operação de quebra de vértice em um determinado vértice u significa substituir algumas das arestas ( u, v) por arestas (u', v), onde u' é um novo vértice. O skewness de G é o número mínimo de arestas que devem ser removidas de G para torná-Io planar. O vertex deletion number de G é o menor inteiro k tal que existe um subgrafo induzido planar de G obtido através da remoção de k vértices de G.Neste trabalho, apr~sentamos valores exatos para o splitting number, o skewness e o vertex deletion number dos grafos Cn x Cm, onde Cn é o circuito simples com n vértices, e para o splitting number e o vertex deletion number de uma triangulação dos grafos Cn x CmAbstract: The splíttíng number of a graph G is the minimum number of splitting steps needed to turn G into a planar graph; where each step replaces some of the edges (u, v) incident to a selected vertex u by edges (u', v), where u' is a new vertex. The skewness of G is the minimum number of edges that need to be deleted from G to produce a planar graph. The vertex deletíon number of G is the smallest integer k such that there is a planar induced subgraph of G obtained by the removal of k vertices of G. In this work, we show exact values for the splíttíng number, skewness and vertex deletíon number of the graphs Cn x Cm, where Cn is the simple circuit on n vertices, and for the splíttíng number and vertex deletíon number of a triangulation of Cn x CmMestradoMestre em Ciencia da Computação