Skewness and the crossing numbers of graphs

Zongpeng Ding; Zongpeng Ding

doi:10.3934/math.20231223

AIMS Mathematics

2023, Volume 8, Issue 10: 23989-23996. doi: 10.3934/math.20231223

Previous Article Next Article

Research article Special Issues

Skewness and the crossing numbers of graphs

Zongpeng Ding ^,

School of Mathematics and Statistics, Hunan First Normal University, Changsha 410205, China

Received: 28 March 2023 Revised: 12 July 2023 Accepted: 21 July 2023 Published: 07 August 2023
MSC : 05C10, 05C62

The skewness of a graph $ G $, $ sk(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 $, $ cr(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 $ sk(G) = cr(G) $.
- drawing,
- skewness,
- crossing number,
- near-planar graph,
- maximal 1-planar graph
Citation: Zongpeng Ding. Skewness and the crossing numbers of graphs[J]. AIMS Mathematics, 2023, 8(10): 23989-23996. doi: 10.3934/math.20231223

Related Papers:

Abstract

The skewness of a graph $ G $, $ sk(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 $, $ cr(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 $ sk(G) = cr(G) $.

References

[1]	M. O. Albertson, Chromatic number, independence ratio, and crossing number, ARS Math. Contemp., 1 (2008), 1–6. https://doi.org/10.26493/1855-3974.10.2d0 doi: 10.26493/1855-3974.10.2d0
[2]	C. Bachmaier, F. J. Brandenburg, K. Hanauer, D. Neuwirth, J. Reislhuber, NIC-planar graphs, Discrete Appl. Math., 232 (2017), 23–40. https://doi.org/10.1016/j.dam.2017.08.015 doi: 10.1016/j.dam.2017.08.015
[3]	J. A. Bondy, U. S. R. Murty, Graph theory, GTM 244, Springer, 2008.
[4]	J. Barát, G. Tóth, Improvements on the density of maximal 1-planar graphs, J. Graph Theory, 88 (2018), 101–109. https://doi.org/10.1002/jgt.22187 doi: 10.1002/jgt.22187
[5]	S. N. Bhatt, F. T. Leighton, A framework for solving VLSI graph layout problems, J. Comput. Syst. Sci., 28 (1984), 300–343. https://doi.org/10.1016/0022-0000(84)90071-0 doi: 10.1016/0022-0000(84)90071-0
[6]	G. L. Chia, K. A. Sim, On the skewness of the join of graphs, Discrete Appl. Math., 161 (2013), 2405–2409. https://doi.org/10.1016/j.dam.2013.03.023 doi: 10.1016/j.dam.2013.03.023
[7]	M. Chimani, C. Gutwenger, Non-planar core reduction of graphs, Discrete Math., 309 (2009), 1838–1855. https://doi.org/10.1016/j.disc.2007.12.078 doi: 10.1016/j.disc.2007.12.078
[8]	R. J. Cimikowski, Graph planarization and skewness, Congr. Numer., 88 (1992), 21–32.
[9]	S. Cabello, B. Mohar, Adding one edge to planar graphs makes crossing number and 1-planarity hard, SIAM J. Comput., 42 (2013), 1803–1829. https://doi.org/10.1137/120872310 doi: 10.1137/120872310
[10]	Z. Ding, Z. Ouyang, Y. Huang, F. M. Dong, New upper bounds for the crossing numbers of crossing-critical graphs, Discrete Math., 345 (2022), 113090. https://doi.org/10.1016/j.disc.2022.113090 doi: 10.1016/j.disc.2022.113090
[11]	M. R. Garey, D. S. Johnson, Crossing number is NP-complete, SIAM J. Algebraic Discrete Methods, 4 (1983), 312–316. https://doi.org/10.1137/0604033 doi: 10.1137/0604033
[12]	A. Liebers, Planarizing graphs–A survey and annotated bibliography, J. Graph Algorithms Appl., 5 (2001), 1–74.
[13]	P. C. Liu, R. C. Geldmacher, On the deletion of nonplanar edges of a graph, Congressus Numerantium, 24 (1979), 727–738.
[14]	D. McQuillan, S. Pan, R. B. Richter, On the crossing number of $K_13$, J. Combin. Theory, Ser. B, 115 (2015), 224–235. https://doi.org/10.1016/j.jctb.2015.06.002 doi: 10.1016/j.jctb.2015.06.002
[15]	M. Schaefer, Crossing numbers of graphs, CRC Press, Florida, 2017.
[16]	X. Zhang, G. Liu, The structure of plane graphs with independent crossings and its application to coloring problems, Centr. Eur. J. Math., 11 (2013), 308–321. https://doi.org/10.2478/s11533-012-0094-7 doi: 10.2478/s11533-012-0094-7

Reader Comments

Your name:*

Email:*
© 2023 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)