A graph G = (V, E) is called 1-planar if it admits a drawing in the plane such that each edge is crossed at most once. In this paper, we study bipartite 1-planar graphs with prescribed numbers of vertices in partite sets. Bipartite 1-planar graphs are known to have at most 3n − 8 edges, where n denotes the order of a graph. We show that maximal-size bipartite 1-planar graphs which are almost balanced have not significantly fewer edges than indicated by this upper bound, while the same is not true for unbalanced ones. We prove that the maximal possible size of bipartite 1-planar graphs whose one partite set is much smaller than the other one tends towards 2n rather than 3n. In particular, we prove that if the size of the smaller partite set is sublinear in n, then |E| = (2 + o(1))n, while the same is not true otherwise.
@article{bwmeta1.element.doi-10_7151_dmgt_1845,
author = {J\'ulius Czap and Jakub Przyby\l o and Erika \v Skrabu\v l\'akov\'a},
title = {On An Extremal Problem In The Class Of Bipartite 1-Planar Graphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {36},
year = {2016},
pages = {141-151},
zbl = {1329.05081},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1845}
}
Július Czap; Jakub Przybyło; Erika Škrabuľáková. On An Extremal Problem In The Class Of Bipartite 1-Planar Graphs. Discussiones Mathematicae Graph Theory, Tome 36 (2016) pp. 141-151. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1845/
[1] F.J. Brandenburg, D. Eppstein, A. Gleißner, M.T. Goodrich, K. Hanauer and J. Reislhuber, On the density of maximal 1-planar graphs, Graph Drawing, Lecture Notes Comput. Sci. 7704 (2013) 327–338. doi:10.1007/978-3-642-36763-2_29[Crossref] | Zbl 06149952
[2] J. Czap and D. Hudák, On drawings and decompositions of 1-planar graphs, Electron. J. Combin. 20 (2013) P54. | Zbl 1295.05084
[3] J. Czap and D. Hudák, 1-planarity of complete multipartite graphs, Discrete Appl. Math. 160 (2012) 505–512. doi:10.1016/j.dam.2011.11.014[Crossref][WoS]
[4] R. Diestel, Graph Theory (Springer, New York, 2010).
[5] I. Fabrici and T. Madaras, The structure of 1-planar graphs, Discrete Math. 307 (2007) 854–865. doi:10.1016/j.disc.2005.11.056[Crossref] | Zbl 1111.05026
[6] D.V. Karpov, An upper bound on the number of edges in an almost planar bipartite graph, J. Math. Sci. 196 (2014) 737–746. doi:10.1007/s10958-014-1690-9[Crossref] | Zbl 1298.05087
[7] J. Pach and G. Tóth, Graphs drawn with few crossings per edge, Combinatorica 17 (1997) 427–439. doi:10.1007/BF01215922[Crossref] | Zbl 0902.05017
[8] H. Bodendiek, R. Schumacher and K. Wagner, Über 1-optimale Graphen, Math. Nachr. 117 (1984) 323–339. doi:10.1002/mana.3211170125[Crossref] | Zbl 0558.05017
[9] É. Sopena, personal communication, Seventh Cracow Conference in Graph Theory, Rytro (2014).