RUS  ENG
Full version
JOURNALS // Zapiski Nauchnykh Seminarov POMI // Archive

Zap. Nauchn. Sem. POMI, 2012 Volume 406, Pages 12–30 (Mi znsl5288)

This article is cited in 9 papers

Upper bound on the number of edges of an almost planar bipartite graph

D. V. Karpov

St. Petersburg Department of V. A. Steklov Institute of Mathematics, Russian Academy of Sciences, St. Petersburg, Russia

Abstract: 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.

Key words and phrases: topological graphs, planar graphs, bipartite graphs.

UDC: 519.173.2

Received: 03.09.2012


 English version:
Journal of Mathematical Sciences (New York), 2014, 196:6, 737–746

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024