On the skewness of the generalized Heawood graphs

Abstract

By the skewness of a graph, we mean the minimum number of its edges whose deletion results in a planar graph. We determine the skewness of a large family of cubic bipartite graphs (which includes the Heawood graph as a special case). Moreover, we also determine those classes of these cubic graphs which are [Formula: see text]-skew whose resulting plane graphs (upon deleting the right minimum number of edges) are hexagulations.

Keywords

• Skewness
• cubic graph
• girth
• hexagulation
• Heawood graph