On the minimum size of maximal IC-plane graphs

Rui Xu; Rui Xu

doi:10.3934/math.2025643

AIMS Mathematics

2025, Volume 10, Issue 6: 14278-14287. doi: 10.3934/math.2025643

Previous Article Next Article

Research article Special Issues

On the minimum size of maximal IC-plane graphs

Rui Xu ^,

Key Laboratory of Computing and Stochastic Mathematics (Ministry of Education), School of Mathematics and Statistics, Hunan Normal University, Changsha, Hunan 410081, China

Received: 03 January 2025 Revised: 20 May 2025 Accepted: 06 June 2025 Published: 23 June 2025
MSC : 05C10

A graph is IC-planar if it admits a drawing with at most one crossing per edge so that each vertex is incident to at most one crossing edge, and an IC-plane graph means such a drawing of an IC-planar graph. We show that any maximal IC-plane graph with $ n $ vertices has at least $ 2n-2 $ edges.
- edge density,
- maximal IC-plane graph
Citation: Rui Xu. On the minimum size of maximal IC-plane graphs[J]. AIMS Mathematics, 2025, 10(6): 14278-14287. doi: 10.3934/math.2025643

Related Papers:

Abstract

A graph is IC-planar if it admits a drawing with at most one crossing per edge so that each vertex is incident to at most one crossing edge, and an IC-plane graph means such a drawing of an IC-planar graph. We show that any maximal IC-plane graph with $ n $ vertices has at least $ 2n-2 $ edges.

References

[1]	Y. Suzuki, Re-embeddings of maximum 1-planar graphs, SIAM J. Discrete Math., 24 (2010), 1527–1540. https://doi.org/10.1137/090746835 doi: 10.1137/090746835
[2]	F. J. Brandenburg, D. Eppstein, A. Gleißner, M. T. Goodrich, K. Hanauer, J. Reislhuber, On the density of maximal 1-planar graphs, In: W. Didimo, M. Patrignani, Graph drawing, Lecture Notes in Computer Science, Springer, Berlin, Heidelberg, 7704 (2013), 327–338. https://doi.org/10.1007/978-3-642-36763-2_29
[3]	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
[4]	Y. Huang, Z. Ouyang, L. Zhang, F. Dong, Determining the minimum size of maximal 1-plane graphs, arXiv Preprint, 2025. https://doi.org/10.48550/arXiv.2502.11696
[5]	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
[6]	F. J. Brandenburg, W. Didimo, W. S. Evans, P. Kindermann, G. Liotta, F. Montecchiani, Recognizing and drawing IC-planar graphs, Theor. Comput. Sci., 636 (2016), 1–16. https://doi.org/10.1016/j.tcs.2016.04.026 doi: 10.1016/j.tcs.2016.04.026
[7]	C. Bachmaier, F. J. Brandenburg, K. Hanauer, A note on IC-planar graphs, arXiv Preprint, 2017. https://doi.org/10.48550/arXiv.1707.08652
[8]	Y. Wang, Y. Wang, W. Wang, L. Zheng, A note on the list vertex-arboricity of IC-planar graphs, Discrete Math., 347 (2024), 113998. https://doi.org/10.1016/j.disc.2024.113998 doi: 10.1016/j.disc.2024.113998
[9]	X. Zhang, G. Liu, The structure of plane graphs with independent crossingsand its application to coloring problems, Cent. Eur. J. Math., 11 (2013), 308–321. https://doi.org/10.2478/s11533-012-0094-7 doi: 10.2478/s11533-012-0094-7
[10]	X. Zhang, Drawing complete multipartite graphs on the plane with restrictions on crossings, Acta Math. Sin.-English Ser., 30 (2014), 2045–2053. https://doi.org/10.1007/s10114-014-3763-6 doi: 10.1007/s10114-014-3763-6
[11]	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
[12]	S. H. Hong, P. Eades, N. Katoh, G. Liotta, P. Schweitzer, Y. Suzuki, A linear-time algorithm for testing outer-1-planarity, Algorithmica, 72 (2015), 1033–1054. https://doi.org/10.1007/s00453-014-9890-8 doi: 10.1007/s00453-014-9890-8
[13]	C. Auer, C. Bachmaier, F. J. Brandenburg, A. Gleißner, K. Hanauer, D. Neuwirth, et al., Outer 1-planar graphs, Algorithmica, 74 (2015), 1293–1320. https://doi.org/10.1007/s00453-015-0002-1 doi: 10.1007/s00453-015-0002-1
[14]	D. B. West, Introduction to graph theory, 2 Eds., Prentice Gall, 2001.

Reader Comments

Your name:*

Email:*
© 2025 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)