On nonplanarity of cubic graphs

Анотація

A cubic graph is nonplanar if and only if it contains a subgraph homeomorphic to K_3,3. For a given 2-connected cubic graph G, denoted by ed(G) the minimal number of edges so that after removal them from G the resulting graph becomes planar and g(G) the genus of G. Moreover, for a given simple graph G let cr(G) denote the minimal number of crossings of edges needed to draw G on the plain (so the minimum is taken over all submersions of G in the plane). In this paper, we study relations between the characteristics ed(G) and g(G) and cr(G) for some special classes of graphs and discuss the problems related with their evaluation.