Publications
Sort:
Open Access Research Article Issue
Skewness and the crossing numbers of graphs
AIMS Mathematics 2023, 8(10): 23989-23996
Published: 15 October 2023
Abstract PDF (1.1 MB) Collect
Downloads:5

The skewness of a graph G, s k ( G ), is the smallest number of edges that need to be removed from G to make it planar. The crossing number of a graph G, c r ( G ), is the minimum number of crossings over all possible drawings of G. There is minimal work concerning the relationship between skewness and crossing numbers. In this work, we first introduce an inequality relation for these two parameters, and then we construct infinitely many near-planar graphs such that the inequality is equal. In addition, we give a necessary and sufficient condition for a graph to have its skewness equal to the crossing number and characterize some special graphs with s k ( G ) = c r ( G ).

Total 1