On nonplanarity of cubic graphs

L. P. Plachta


A cubic graph is nonplanar if and only if it contains a subgraph homeomorphic to K3,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.

Повний текст: PDF


  • Поки немає зовнішніх посилань.

Creative Commons License
Ця робота ліцензована Creative Commons Attribution 3.0 License.