Geodesic
Upper bound on the number of edges of an almost planar bipartite graph
Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part V, Tome 406 (2012), pp. 12-30 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

Let $G$ be a bipartite graph without loops and multiple edges on $v\ge4$ vertices, which can be drawn on the plane such that any edge intersects at most one other edge. We prove that such graph has at most $3v-8$ edges for even $v\ne6$ and at most $3v-9$ edges for odd $v$ and $v=6$. For all $v\ge4$ examples showing that these bounds are tight are constructed. In the end of the paper, we discuss a question about drawings of complete bipartite graphs on the plane such that any edge intersects at most one other edge. 
@article{ZNSL_2012_406_a1,
     author = {D. V. Karpov},
     title = {Upper bound on the number of edges of an almost planar bipartite graph},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {12--30},
     year = {2012},
     volume = {406},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2012_406_a1/}
}
TY  - JOUR
AU  - D. V. Karpov
TI  - Upper bound on the number of edges of an almost planar bipartite graph
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2012
SP  - 12
EP  - 30
VL  - 406
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2012_406_a1/
LA  - ru
ID  - ZNSL_2012_406_a1
ER  - 
%0 Journal Article
%A D. V. Karpov
%T Upper bound on the number of edges of an almost planar bipartite graph
%J Zapiski Nauchnykh Seminarov POMI
%D 2012
%P 12-30
%V 406
%U http://geodesic.mathdoc.fr/item/ZNSL_2012_406_a1/
%G ru
%F ZNSL_2012_406_a1
D. V. Karpov. Upper bound on the number of edges of an almost planar bipartite graph. Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part V, Tome 406 (2012), pp. 12-30. http://geodesic.mathdoc.fr/item/ZNSL_2012_406_a1/

[1] J. Pach, G. Tóth, “Graphs drawn with few crossing per edge”, Combinatorica, 17:3 (1997), 427–439 | DOI | MR | Zbl

[2] P. K. Agarwal, B. Aronov, J. Pach, R. Pollack, M. Sharir, “Quasi-planar graphs have a linear number of edges”, Combinatorica, 17:1 (1997), 1–9 | DOI | MR | Zbl

[3] E. Ackerman, G. Tardos, “On the maximum number of edges in quasi-planar graphs”, J. Comb. Theory Ser. A, 114:3 (2007), 563–571 | DOI | MR | Zbl

[4] E. Ackerman, “On the maximum number of edges in topological graphs with no four pairwise crossing edges”, Discrete Comput. Geom., 41:3 (2009), 365–375 | DOI | MR | Zbl

[5] G. Tardos, G. Tóth, “Crossing stars in topological graphs”, SIAM J. Discrete Math., 21:3 (2007), 737–749 | DOI | MR | Zbl

[6] J. Pach, R. Pinchasi, G. Tardos, G. Tóth, “Geometric graphs with no self-intersecting path of length three”, (English summary), European J. Combin., 25:6 (2004), 793–811 | DOI | MR | Zbl