@techreport{men-xav-far-fig-sto-99-vdel-tr, author = {C{\^a}ndido F. Xavier de {Mendon{\c{c}}a Neto} and {\'E}rico F. {Xavier} and Lu{\'e}rbio Faria and Celina M. H. de Figueiredo and Jorge Stolfi}, title = {The Vertex Deletion Number of {$C_n \times C_m$}}, institution = {Institute of Computing, Univ. of Campinas}, number = {IC-99-14}, pages = {39}, year = 1999, month = may, abstract = {The vertex deletion number of a graph $G$ is the smallest integer $k \geq 0$ such that there is a planar induced subgraph of $G$ obtained by the removal of $k$ vertices from $G$. In this work we study the vertex deletion number of $C_n\times C_m$, the rectangular grid with toroidal topology. We prove the extact result $\min\{n,m\} - \xi_{5,9}(n,m)$, where $\xi_{i,j}(k_1,k_2)$ is the number of true conditions among the following: (i) $k_1 = k_2 \leq i$ and (ii) $k_1 + k_2 \leq j$.} }