Graph Skewness

The skewness of a graph  is the minimum number of edges whose removal results in a planar graph (Harary 1994, p. 124). The skewness is sometimes denoted  (Cimikowski 1992).

A graph  with  has toroidal crossing number . (However, there exist graphs with  that still have .)

 satisfies

(1)

where  is the vertex count of  and  its edge count (Cimikowski 1992).

The skewness of a disconnected graph is equal to the sum of skewnesses of its connected components.

The skewness of a complete graph  is given by

(2)

of the complete bipartite graph  by

(3)

and of the hypercube graph  by

(4)

(Cimikowski 1992).

REFERENCES

Chia, G. L. and Sim, K. A. "On the Skewness of the Join of Graphs." Disc. Appl. Math. 161, 2405-2409, 2013.

Cimikowski, R. J. "Graph Planarization and Skewness. In Proceedings of the Twenty-third Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1992). Congr. Numer., 88, 21-32, 1992.

Harary, F. Problem 11.24 in Graph Theory. Reading, MA: Addison-Wesley, p. 124, 1994.