Geodesic
On An Extremal Problem In The Class Of Bipartite 1-Planar Graphs
Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 1, pp. 141-151.

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: 1-planar graph, bipartite graph, graph size 
@article{DMGT_2016_36_1_a10,
     author = {Czap, J\'ulius and Przyby{\l}o, Jakub and \v{S}krabu\v{l}\'akov\'a, Erika},
     title = {On {An} {Extremal} {Problem} {In} {The} {Class} {Of} {Bipartite} {1-Planar} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {141--151},
     publisher = {mathdoc},
     volume = {36},
     number = {1},
     year = {2016},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2016_36_1_a10/}
}
TY  - JOUR
AU  - Czap, Július
AU  - Przybyło, Jakub
AU  - Škrabuľáková, Erika
TI  - On An Extremal Problem In The Class Of Bipartite 1-Planar Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2016
SP  - 141
EP  - 151
VL  - 36
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2016_36_1_a10/
LA  - en
ID  - DMGT_2016_36_1_a10
ER  - 
%0 Journal Article
%A Czap, Július
%A Przybyło, Jakub
%A Škrabuľáková, Erika
%T On An Extremal Problem In The Class Of Bipartite 1-Planar Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2016
%P 141-151
%V 36
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2016_36_1_a10/
%G en
%F DMGT_2016_36_1_a10
Czap, Július; Przybyło, Jakub; Škrabuľáková, Erika. On An Extremal Problem In The Class Of Bipartite 1-Planar Graphs. Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 1, pp. 141-151. http://geodesic.mathdoc.fr/item/DMGT_2016_36_1_a10/

[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

[2] J. Czap and D. Hudák, On drawings and decompositions of 1- planar graphs, Electron. J. Combin. 20 (2013) P54.

[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

[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

[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

[7] J. Pach and G. Tóth, Graphs drawn with few crossings per edge, Combinatorica 17 (1997) 427–439. doi:10.1007/BF01215922

[8] H. Bodendiek, R. Schumacher and K. Wagner, Über 1- optimale Graphen, Math. Nachr. 117 (1984) 323–339. doi:10.1002/mana.3211170125

[9] É. Sopena, personal communication, Seventh Cracow Conference in Graph Theory, Rytro (2014).