The Non Planar Vertex Deletion of \(C_n \times C_m\)

Abstract

The non-planar vertex deletion or vertex deletion \(vd(G)\) of a graph \(G = (V, E)\) is the smallest non-negative integer \(k\) such that the removal of \(k\) vertices from \(G\) produces a planar graph. Hence, the maximum planar induced subgraph of \(G\) has precisely \(|V| – vd(G)\) vertices. The problem of computing vertex deletion is in general very hard; it is NP-complete. In this paper, we compute the non-planar vertex deletion for the family of toroidal graphs \(C_n \times C_m\).