TOPICS
Search

Graph Skewness


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

A graph G with mu(G)<2 has toroidal crossing number cr_(1)(G)=0. (However, there exist graphs with mu(G)>=2 that still have cr_(1)(G)=0.)

mu(G) satisfies

 mu(G)>=m-(3n-6),
(1)

where n>2 is the vertex count of G and m 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 K_n is given by

 mu(K_n)={0   for n<=4; 1/2(n-3)(n-4)   otherwise,
(2)

of the complete bipartite graph K_(m,n) by

 mu(K_(m,n))=mn-2(m+n)+4,
(3)

and of the hypercube graph Q_n by

 mu(Q_n)={0   for n<=3; 2^n(n-2)-n·2^(n-1)+4   otherwise
(4)

(Cimikowski 1992).


See also

Apex Graph, Critical Nonplanar Graph, Graph Coarseness, Planar Graph, Toroidal Crossing Number, Toroidal Graph

Explore with Wolfram|Alpha

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.

Cite this as:

Weisstein, Eric W. "Graph Skewness." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/GraphSkewness.html

Subject classifications