On measures of nonplanarity of cubic graphs

Abstract

We study two measures of nonplanarity of cubic graphs G, the genus γ (G), and the edge deletion number ed(G). For cubic graphs of small orders these parameters are compared with another measure of nonplanarity, the rectilinear crossing number (G). We introduce operations of connected sum, specified for cubic graphs G, and show that under certain conditions the parameters γ(G) and ed(G) are additive (subadditive) with respect to them.The minimal genus graphs (i.e. the cubic graphs of minimum order with given value of genus γ) and the minimal edge deletion graphs (i.e. cubic graphs of minimum order with given value of edge deletion number ed) are introduced and studied. We provide upper bounds for the order of minimal genus and minimal edge deletion graphs.